给你一个 $$$n$$$ 整数数组 $$$a_1,a_2,\ldots,a_n$$$。您还会获得一个数组 $$$p_1, p_2, \ldots, p_n$$$。
让 $$$S$$$ 表示随机多重集(即,它可能包含相等的元素),构造如下:
- 最初,$$$S$$$ 是空的。
- 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,将 $$$a_i$$$ 插入到 $$$S$$$ 中,概率为 $$$\frac{p_i}{10^4}$$$。请注意,每个元素都是独立插入的。
将 $$$f(S)$$$ 表示为 $$$S$$$ 的所有元素的按位异或。请计算$$$(f(S))^2$$$的期望值。输出对 $$$10^9 + 7$$$ 取模的答案。
正式地,让 $$$M = 10^9 + 7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1023$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le 10^4$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$(f(S))^2$$$ 的期望值,模 $$$10^9 + 7$$$。
示例
输入 #1
4 2 1 2 5000 5000 2 1 1 1000 2000 6 343 624 675 451 902 820 6536 5326 7648 2165 9430 5428 1 1 10000
输出 #1
500000007 820000006 280120536 1
注意
在第一个测试用例中,$$$a = [1, 2]$$$,并且每个元素以 $$$\frac{1}{2}$$$ 的概率插入到 $$$S$$$ 中,因为 $$$p_1 = p_2 = 5000$$$ 且 $$$\frac{p_i}{10^4} = \frac{1}{2}$$$。因此,$$$S$$$ 有 $$$4$$$ 个结果,每个结果的发生概率相同 $$$\frac{1}{4}$$$:
- $$$S = \var没有$$$。在这种情况下,$$$f(S) = 0$$$,$$$(f(S))^2 = 0$$$。
- $$$S = \{1\}$$$。在这种情况下,$$$f(S) = 1$$$,$$$(f(S))^2 = 1$$$。
- $$$S = \{2\}$$$。在这种情况下,$$$f(S) = 2$$$,$$$(f(S))^2 = 4$$$。
- $$$S = \{1,2\}$$$。在这种情况下,$$$f(S) = 1 \oplus 2 = 3$$$,$$$(f(S))^2 = 9$$$。
因此,答案是 $$$0 \cdot \frac{1}{4} + 1 \cdot \frac{1}{4} + 4\cdot \frac{1}{4} + 9 \cdot \frac{1}{4} = \frac{14}{4} = \frac{7}{2} \equiv 500\,000\,007 \pmod{10^9 + 7}$$$。
在第二个测试用例中,$$$a = [1, 1]$$$,$$$a_1$$$ 以 $$$0.1$$$ 的概率插入 $$$S$$$,而 $$$a_2$$$ 以 $$$0.2$$$ 的概率插入 $$$S$$$。 $$$S$$$ 有 $$$3$$$ 结果:
- $$$S = \var没有$$$。在这种情况下,$$$f(S) = 0$$$,$$$(f(S))^2 = 0$$$。这种情况发生的概率为 $$$(1-0.1) \cdot (1-0.2) = 0.72$$$。
- $$$S = \{1\}$$$。在这种情况下,$$$f(S) = 1$$$,$$$(f(S))^2 = 1$$$。这种情况发生的概率为 $$$(1-0.1) \cdot 0.2 + 0.1 \cdot (1-0.2) = 0.26$$$。
- $$$S = \{1, 1\}$$$。在这种情况下,$$$f(S) = 0$$$,$$$(f(S))^2 = 0$$$。这种情况发生的概率为 $$$0.1 \cdot 0.2 = 0.02$$$。
因此,答案是 $$$0 \cdot 0.72 + 1 \cdot 0.26 + 0 \cdot 0.02 = 0.26 = \frac{26}{100} \equiv 820\,000\,006 \pmod{10^9 + 7}$$$。