P17091 三十四万一千七百九十九

**请留意本题特殊的时间限制**。**请选手注意常数因子对程序运行效率带来的影响**。 --- 本故事纯属虚构，如有雷同，纯属巧合。 > 苏苏压根没加甲鱼的 QQ。数学课上，贝壳坐她前面，突然贼兮兮地转过头：“苏苏，甲鱼把 QQ 名改了。” > > “改成什么？” > > “我爱苏苏。” > > 苏苏脸一沉：“莫名其妙。” > > 话音刚落，数学老师猛地一回头——然而下一秒，他反而笑了：“甲鱼啊，想找另一半，好歹学学二次函数——人家有个对称轴，左右各一半。你这‘我爱苏苏’，连个对称性都没有，纯属单项式——单相思嘛。真要表白，用心形线才够浪漫。” > > 苏苏哭笑不得：“老师，您这是教数学还是教红娘？” > > 老师推了推眼镜：“曲线救国，懂不懂？直线球你又不接。再说了，这叫‘数中自有颜如玉’。” > > 

Sirus 拿到了一个长度为 $n$ 的非负整数序列 $a$。TA 需要将这 $n$ 个整数划分到两个可重集合 $S_1$ 和 $S_2$ 中。注意，$S_1$ 和 $S_2$ 可以为空集。 随后，TA 会把 $S_1,S_2$ 这两个集合丢给 Dylan。Dylan 在知道划分方案的前提下，会按照如下流程进行操作： - 准备一个初始为空的序列 $r$。 - 设初始时两个集合大小分别为 $s_1,s_2$。随后依次执行如下操作共 $\max(s_1,s_2)$ 轮： - 若 $S_1$ 非空，则在 $S_1$ 中任选一个元素作为 $x$ 并删去；否则取 $x=0$。 - 若 $S_2$ 非空，则在 $S_2$ 中任选一个元素作为 $y$ 并删去；否则取 $y=0$。 - 在数列 $r$ 的末尾加入 $x\oplus y$。 其中，$\oplus$ 表示按位异或运算。 现在，Sirus 和 Dylan 会按照如上规则玩两次游戏： - 对于第一次游戏，Sirus 和 Dylan 都希望最小化 $r$ 的字典序。 - 对于第二次游戏，Sirus 希望最大化 $r$ 的字典序，Dylan 希望最小化 $r$ 的字典序。 其中：对于两个序列 $a,b$，称 $a$ 的字典序小于 $b$，当且仅当存在最小的正整数 $p$ 满足 $a_p\ne b_p$，且有 $a_p

**本题有多组测试数据**。 第一行一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行一个正整数 $n$。 第二行包含 $n$ 个非负整数 $a_i$。

对于每组测试数据，输出一行两个非负整数，分别表示第一次游戏和第二次游戏过后 $$ \left(\sum_{i=1}^{|r|} (r_i+1)\times i\right) \pmod {10^9+7} $$ 的值。 两个整数之间用一个空格隔开。

#### 样例 $1$ 解释 考虑样例 $1$ 中的第一组测试数据 $a=[2,3,16,18]$。 在第一次游戏中，Sirus 会选择 $S_1=\{2,16\},S_2=\{3,18\}$ 的划分方式。 Dylan 会依次进行如下操作： - 选出 $x=2\in S_1,y=3\in S_2$，此时 $x\oplus y=1$。操作过后，$r=[1],S_1=\{16\},S_2=\{18\}$。 - 选出 $x=16\in S_1,y=18\in S_2$，此时 $x\oplus y=2$。操作过后，$r=[1,2],S_1=S_2=\emptyset$。 在第二次游戏中，Sirus 会选择 $S_1=\{2,3\},S_2=\{16,18\}$ 的划分方式。 Dylan 会依次进行如下操作： - 选出 $x=2\in S_1,y=18\in S_2$，此时 $x\oplus y=16$。操作过后，$r=[16],S_1=\{3\},S_2=\{16\}$。 - 选出 $x=3\in S_1,y=16\in S_2$，此时 $x\oplus y=19$。操作过后，$r=[16,19],S_1=S_2=\emptyset$。 对于第二组测试数据，在第一次游戏过后，$r=[0,1,18,30]$；在第二次游戏过后，$r=[16,28,1]$。 对于第三组测试数据，在第一次游戏过后，$r=[0,0,0,0,2,5,8]$；在第二次游戏过后，$r=[8,10,10,2,4,4,5]$。 对于第四组测试数据，在第一次游戏过后，$r=[0,0,0,0,0,3,5,7]$；在第二次游戏过后，$r=[8,8,9,10,4,4,5,7]$。 #### 数据范围 **本题采用捆绑测试**。 对于 $100\%$ 的数据，保证： - $1\le T,n\le 10^6$。 - $\sum n\le 10^6$。 - $0\le a_i\le 2^{30}-1$。 ::cute-table{tuack} | 子任务编号 | 分值 | $\sum n \le$ | $a_i \le$ | 特殊性质 | 时间限制 | | :----------: | :----: | :------------: | :----------: | :----------: | :-:| | $1$ | $10$ | $10$ | $100$ | 无 | $1000\text{ ms}$ | $2$ | $5$ | $2\times 10^3$ | $2^{30}-1$ | $\text{A}$ | $2000\text{ ms}$ | $3$ | $15$ | ^ | ^ | $\text{BC}$ |^| | $4$ | $35$ | ^ | ^ | $\text{C}$ |^ | | $5$ | $20$ | ^ | ^ | 无 |^| | $6$ | $15$ | $10^6$ | ^ | ^ |$5000\text{ ms}$| 特殊性质 $\text{A}$：保证所有 $a_i$ 均相同。 特殊性质 $\text{B}$：保证 $\min \{a_i\}\ge 2^{29}$。 特殊性质 $\text{C}$：保证 $\min \{a_i\}\ge 1$。 **特别地**，对于每一个子任务： - 若您能够对其中所有测试数据正确求出两次游戏的结果，则您可以获得该子任务 $100\%$ 的分数。 - 若您能够对其中所有测试数据正确求出第一次游戏的结果，而未能对其中所有测试数据正确求出第二次游戏的结果，则您可以获得该子任务 $60\%$ 的分数。 - 若您能够对其中所有测试数据正确求出第二次游戏的结果，而未能对其中所有测试数据正确求出第一次游戏的结果，则您可以获得该子任务 $45\%$ 的分数。 - 否则，您可以获得该子任务 $0\%$ 的分数。 最终，您的总分为各子任务的得分相加后向下取整的结果，您程序的用时为各个测试点运行用时的最大值。 **注意**，对于每组测试数据，即使您只打算回答其中一个游戏的结果，也仍需按照格式输出一行两个整数。