6865：Kidnapper's Matching Problem

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.

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

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.