Tomoyuki-Mizuyama 有一个 \(n\)（\(2\le n\le 10^5\)）个数的序列。现在他想做若干次操作，每次选择两个数，把他们异或起来，之后删除这两个数，并把他们异或后的结果加入序列。他进行若干次操作后，会把序列中剩下的数全部乘起来。他想知道最后的结果最大是多少。注意，Tomoyuki-Mizuyama 最多操作 \(n-1\) 次，在这之后序列可能会只剩下一个数。由于答案可能很大，输出对 \(1000000007\) 取模后的结果。（\(1\le a_i\le10^9\)）
一个显然的贪心思路：当且仅当两个数的异或和大于他们的乘积时我们才去合并。如果暴力判断的话，复杂度是 \(\mathcal{O}(n^3)\)（口胡的），显然不行，我们尝试去找一个规律。
先抛结论：$$a\oplus b>a\times b\iff a=1,b\equiv0(\bmod 2)$$
首先充分性很好证明，一眼出，接下来证必要性。
设两个正整数 \(a\)、\(b\)，\(a\) 在二进制下有 \(n\) 位，\(b\) 在二进制下有 \(m\) 位，不妨设 \(n\ge m\)，首先 \(n=1\) 或者 \(m=1\) 的时候直接枚举即可，这里讨论 \(n\ge m\ge2\) 的情况。
我们可以得到 \(a\oplus b\) 的最大值是类似于 \((\overbrace{111\cdots1}^{n\text{个}})_2\) 的形式，也就是 \(2^0+2^1+\cdots+2^{n-1}=2^n-1\)，同时 \(a\times b\) 的最小值是类似于 \((1\overbrace{0\cdots000}^{n-1\text{个}})_2\times(1\overbrace{0\cdots000}^{m-1\text{个}})_2\) 的形式，也就是 \(2^{n-1}\times2^{m-1}=2^{n+m-2}\)，我们知道 \(m\ge2\)，那么 \(n+m-2\ge n\)，那么 \(2^{n+m-2}\ge2^n>2^n-1\)，这就说明当 \(n\ge m\ge2\) 时，\(a\times b\) 的最小值一定大于 \(a\oplus b\) 的最大值，那么 \(a\oplus b<a\times b\)，得证，此时合并一定不优。
所以我们只需要寻找 \(1\) 和与之匹配的偶数即可，还有一个问题：对于两个偶数 \(a,b\) 且 \(a< b\)，我们是选择让 \(a\) 异或 \(1\) 还是 \(b\)？显然选更小的，手模可以发现 \((1\oplus a)\times b > (1\oplus b)\times a\)，所以我们从小到大排序即可。
最后，我们是否用管合并后新加入的数？显然不用，因为合并（异或 \(1\)）之后这个数一定就变成了奇数，再次被合并的话肯定不优。
代码：
read (n) ;
f (i ,1 ,n ,1) {
read (a[i]) ;
if (a[i] == 1) num ++ ;
}
sort (a + 1 ,a + n + 1) ;
f (i ,1 ,n ,1) {
if (a[i] == 1) continue ;
if (a[i] & 1 || ! num) {
(ans *= a[i]) %= mod ;
}
else {
(ans *= 1 ^ a[i]) %= mod ;
num -- ;
}
}