### 问题描述 小然在进行一项二进制寻宝任务。他有一个长度为 $N$ 的二进制字符串 $S$。 他的任务是从中找到两个等长的子串，使得他们的异或值最大。 更具体地说，小然需要找到四个整数 $L1$、$R1$、$L2$、$R2$，满足： - $1 \leq L1 \leq R1 \leq N$ 和 $1 \leq L2 \leq R2 \leq N$； - $|(R1 - L1 + 1)| = |(R2 - L2 + 1)|$，即两个子串的长度相等； - $S_{L1...R1} \oplus S_{L2...R2}$ 的值最大，其中 $\oplus$ 表示异或操作。 请你帮助小然完成这项任务，找到最大的异或值，并以十进制形式输出。由于最大异或值可能很大，请你输出它模 $10^9 + 7$ 的结果。 注意，一个字符串的子串是通过从字符串的头部和/或尾部删除一些（可能为零或全部）字符得到的。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例由两行组成： - 第一行包含一个整数 $N$，表示二进制字符串的长度。 - 第二行包含一个长度为 $N$ 的二进制字符串，由 0 和 1 组成。 ### 输出格式 对于每个测试用例，输出一行一个整数，表示最大的异或值模 $10^9 + 7$ 的结果。 ### 样例输入 ```text 3 4 1010 5 11111 3 011 ``` ### 样例输出 ```text 7 0 2 ``` ### 说明 在第一个测试用例中，我们可以选择 $L1 = 1, R1 = 3, L2 = 2, R2 = 4$。这样，选出的子串是 $101$ 和 $010$，它们的异或值是 $111$，对应的十进制数是 $7$。 在第二个测试用例中，无论我们如何选择，得到的异或值都是 $0$。 在第三个测试用例中，我们可以选择 $L1 = 1, R1 = 2, L2 = 2, R2 = 3$。这样，选出的子串是 $01$ 和 $11$，它们的异或值是 $10$，对应的十进制数是 $2$。 ### 评测数据范围 $1 \leq T \leq 10^3$。 $2 \leq N \leq 10^6$。 所有测试用例中 $N$ 的总和不超过 $2 \times 10^6$。