E. Expected Power
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$. You are also given an array $$$p_1, p_2, \ldots, p_n$$$.

Let $$$S$$$ denote the random multiset (i. e., it may contain equal elements) constructed as follows:

  • Initially, $$$S$$$ is empty.
  • For each $$$i$$$ from $$$1$$$ to $$$n$$$, insert $$$a_i$$$ into $$$S$$$ with probability $$$\frac{p_i}{10^4}$$$. Note that each element is inserted independently.

Denote $$$f(S)$$$ as the bitwise XOR of all elements of $$$S$$$. Please calculate the expected value of $$$(f(S))^2$$$. Output the answer modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 1023$$$).

The third line of each test case contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le 10^4$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the expected value of $$$(f(S))^2$$$, modulo $$$10^9 + 7$$$.

Example
Input
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
Output
500000007
820000006
280120536
1
Note

In the first test case, $$$a = [1, 2]$$$ and each element is inserted into $$$S$$$ with probability $$$\frac{1}{2}$$$, since $$$p_1 = p_2 = 5000$$$ and $$$\frac{p_i}{10^4} = \frac{1}{2}$$$. Thus, there are $$$4$$$ outcomes for $$$S$$$, each happening with the same probability of $$$\frac{1}{4}$$$:

  • $$$S = \varnothing$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$.
  • $$$S = \{1\}$$$. In this case, $$$f(S) = 1$$$, $$$(f(S))^2 = 1$$$.
  • $$$S = \{2\}$$$. In this case, $$$f(S) = 2$$$, $$$(f(S))^2 = 4$$$.
  • $$$S = \{1,2\}$$$. In this case, $$$f(S) = 1 \oplus 2 = 3$$$, $$$(f(S))^2 = 9$$$.

Hence, the answer is $$$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}$$$.

In the second test case, $$$a = [1, 1]$$$, $$$a_1$$$ is inserted into $$$S$$$ with probability $$$0.1$$$, while $$$a_2$$$ is inserted into $$$S$$$ with probability $$$0.2$$$. There are $$$3$$$ outcomes for $$$S$$$:

  • $$$S = \varnothing$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. This happens with probability $$$(1-0.1) \cdot (1-0.2) = 0.72$$$.
  • $$$S = \{1\}$$$. In this case, $$$f(S) = 1$$$, $$$(f(S))^2 = 1$$$. This happens with probability $$$(1-0.1) \cdot 0.2 + 0.1 \cdot (1-0.2) = 0.26$$$.
  • $$$S = \{1, 1\}$$$. In this case, $$$f(S) = 0$$$, $$$(f(S))^2 = 0$$$. This happens with probability $$$0.1 \cdot 0.2 = 0.02$$$.

Hence, the answer is $$$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}$$$.