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$.

见题面 Input 部分

见题面 Output 部分

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}$.