{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cb\u003eIt is preferrable to read the pdf statment.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eOne 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.\u003cbr\u003e\u003cbr\u003eFirst of all, he shall give you a \u003cb\u003epair\u003c/b\u003e of sequences $a$ and $b$, with length $n$ and $m$ respectively.\u003cbr\u003e\u003cbr\u003eGiven that $a$ and $b$ do not necessarily have the same length, they do not exactly make a \u003cb\u003epair\u003c/b\u003e. 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$.\u003cbr\u003e\u003cbr\u003eFor each pair $(a_l, a_{l + 1}, \\ldots, a_{l + m - 1}; b)$, we say they are xor-matched if their \u003cb\u003epairwise-xor\u003c/b\u003e\u0027s 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 \u003cb\u003exor-sum\u003c/b\u003e of $S$\u0027s subsets, i.e.,\u003cbr\u003e\u003cbr\u003e$$2_{\\oplus}^{S} \u003d \\{ t | t \u003d \\bigoplus_{w \\in X} w, X \\subseteq S \\}$$\u003cbr\u003e\u003cbr\u003eNote that, since $\\{\\}$ is always a valid subset of $S$, $0$ is always included in $2_{\\oplus}^{S}$.\u003cbr\u003e\u003cbr\u003eNow Cuber QQ wants you to tell him, for which $l$\u0027s, $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.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$ ($1 \\le T \\le 2 \\cdot 10^4$), denotes the number of test cases.\u003cbr\u003e\u003cbr\u003eEach 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$.\u003cbr\u003e\u003cbr\u003eThe next line contains $n$ space-separated integers $a_1, a_2, \\cdots, a_n$ ($0 \\le a_i \u0026lt; 2^{30}$).\u003cbr\u003e\u003cbr\u003eThe next line contains $m$ space-separated integers $b_1, b_2, \\cdots, b_m$ ($0 \\le b_i \u0026lt; 2^{30}$).\u003cbr\u003e\u003cbr\u003eThe last line contains $k$ space-separated integers $S_1, S_2, \\cdots, S_k$ ($0 \\le S_i \u0026lt; 2^{30}$).\u003cbr\u003e\u003cbr\u003eIt 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$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each case, you should output:\u003cbr\u003e\u003cbr\u003e$$\\\\\\sum_{i \u003d 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)\\\\$$\u003cbr\u003e\u003cbr\u003ewhere $[\\text{condition}]$ equals 1 if $\\text{condition}$ holds and $0$ otherwise."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 2 2\r\n2 5 7 6\r\n3 4\r\n5 6\r\n13 3 3\r\n1 1 4 5 1 4 1 9 1 9 8 1 0\r\n2 5 1\r\n1 2 15\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n80\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}