Problem Statement

For an integer sequence $a$ and a pair of integers $(l, r)$, let $\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$. Here, $a\ xor\ b$ is the bitwise xor of $a$ and $b$.
You are given a sequence $a_1, a_2, \dots, a_N$ of length $N$ and a sequence $b_1, b_2, \dots, b_M$ of length $M$.
Find the number of tuples of integers $(n, u, l_1, l_2)$ that satisfy the following condition.

• $\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)$

Constraints

• $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)$
• All inputs are integers.

Input

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

Output

Output on one line the number of integer tuples satisfying the condition, $mod\ (10^9+7)$. End the output with a newline.

Sample

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