問題文

ある整数列 $a$ と整数の組 $(l, r)$ について、 $\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$ とします。ここで $a\ xor\ b$ は $a$ と $b$ の bitwise xor です。
長さ $N$ の数列 $a_1, a_2, \dots, a_N$ と長さ $M$ の数列 $b_1, b_2, \dots, b_M$ が与えられます。
以下の条件を満たす整数の組 $(n, u, l_1, l_2)$ の数を求めてください。

• $\displaystyle \bigoplus_{x = n}^{u} a_x\ xor\ \displaystyle \bigoplus_{y = l_1}^{l_2} b_y = K\ (1 \le n \le u \le N, 1 \le l_1 \le l_2 \le M)$

制約

• $1 \le N, M \le 2 \times 10^5$
• $0 \le a_i, b_j, K < 1024 = 2^{10}(1 \le i \le N, 1 \le j \le M)$
• 入力はすべて整数

入力

$N\ M\ K$
$a_1\ a_2\ \dots\ a_N$
$b_1\ b_2\ \dots\ b_M$

出力

条件を満たす整数の組の数 $mod\ (10^9+7)$ を一行に出力してください。最後に改行してください。

サンプル

3 3 0
1 2 3
3 4 5

5

10 10 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

3025

14 15 213
363 836 692 58 166 525 170 143 844 457 761 36 395 191
441 941 303 945 986 379 588 946 808 262 672 10 503 901 806

21