E. Expected Powertime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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}$$$.InputEach 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$$$.OutputFor each test case, output the expected value of $$$(f(S))^2$$$, modulo $$$10^9 + 7$$$.ExampleInput421 25000 500021 11000 20006343 624 675 451 902 8206536 5326 7648 2165 9430 54281110000Output500000007
820000006
280120536
1
NoteIn 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}$$$.