Kidnapper's Matching Problem

Problem Description

It is preferrable to read the pdf statment. One day when you were sitting in the couch and eating chips, a guy called you, who claimed that his name was Cuber QQ and he had your girlfriend kidnapped. This seems quite unlikely to you because you do not even have a girlfriend. However, to kill the boring time of Sunday afternoon, you asked how much the ransom is. Surprisingly, Cuber QQ is not interested in your money, the ransom is the answer to a matching problem. It turns out that Cuber QQ is a lover of binary operators, xor especially. First of all, he shall give you a pair of sequences $a$ and $b$, with length $n$ and $m$ respectively. Given that $a$ and $b$ do not necessarily have the same length, they do not exactly make a pair . Therefore consecutive subsequences of $a$ are used to make pairs with $b$, That makes $n-m+1$ pairs: $a_l, a_{l + 1}, \ldots, a_{l + m - 1}$ and $b$ for all $1 \le l \le n-m+1$. For each pair $(a_l, a_{l + 1}, \ldots, a_{l + m - 1}; b)$, we say they are xor-matched if their pairwise-xor 's are all available in a pre-defined set $S$. Concretely, the pair is a match if and only if $a_{l+i-1} \oplus b_i \in 2_{\oplus}^{S}$ of all $1 \le i \le m$. $2_{\oplus}^{S}$ is defined as the set of all possible xor-sum of $S$'s subsets, i.e.,

$$2_{\oplus}^{S} = \{ t | t = \bigoplus_{w \in X} w, X \subseteq S \} $$

Note that, since $\{\}$ is always a valid subset of $S$, $0$ is always included in $2_{\oplus}^{S}$. Now Cuber QQ wants you to tell him, for which $l$'s, $a_l, a_{l + 1}, \cdots, a_{l + m - 1}$ makes a match with $b$. He is not sending your illusory girlfriend back before you correctly answer his question.

Input

The first line contains an integer $T$ ($1 \le T \le 2 \cdot 10^4$), denotes the number of test cases. Each test case begins with three space-separated integers $n$ ($1 \le n \le 2 \cdot 10^5$), $m$ ($1 \le m \le \min(n, 5 \cdot 10^4$)) and $k$ ($1 \le k \le 100$), denoting the lengths of $a$, $b$ and the size of $S$. The next line contains $n$ space-separated integers $a_1, a_2, \cdots, a_n$ ($0 \le a_i < 2^{30}$). The next line contains $m$ space-separated integers $b_1, b_2, \cdots, b_m$ ($0 \le b_i < 2^{30}$). The last line contains $k$ space-separated integers $S_1, S_2, \cdots, S_k$ ($0 \le S_i < 2^{30}$). It is guaranteed that $\sum n \le 1.2 \cdot 10^6, \sum m \le 3 \cdot 10^5, \sum k \le 6 \cdot 10^5$.

Output

For each case, you should output:

$$\sum_{i = 1}^{n - m + 1} [(a_i, a_{i + 1}, \cdots, a_{i + m - 1}) \text{ matches } b] \cdot 2^{i - 1} \bmod (10^9 + 7) $$

where $[\text{condition}]$ equals 1 if $\text{condition}$ holds and $0$ otherwise.

Sample Input

2
4 2 2
2 5 7 6
3 4
5 6
13 3 3
1 1 4 5 1 4 1 9 1 9 8 1 0
2 5 1
1 2 15

Sample Output

2
80

Source

2020 Multi-University Training Contest 8