Problem Statement

heno has an integer sequence $A_1,\ A_2,\cdots ,\ A_N$ of length $N$ and an integer $X$. heno was thinking about the following problem.

"Choose 0 or more integers from $A_1,\ A_2,\cdots ,A_N$ and compute the bitwise XOR of all the chosen integers. How many ways are there to choose the integers so that the result is $X$?"

Since heno loves XOR, this problem was a little too easy for him. So he decided to add $M$ more conditions, each expressed in one of the following forms.

• $0\ l\ r\ $: The number of integers chosen from $A_l,\ A_{l+1},\cdots ,\ A_r$ is even (it may be 0).
• $1\ l\ r\ $: The number of integers chosen from $A_l,\ A_{l+1},\cdots ,\ A_r$ is odd.

Input

$N\ M\ X$
$A_1 A_2 \cdots A_N$
$type_1\ l_1\ r_1$
$type_2\ l_2\ r_2$
$\vdots$
$type_M\ l_M\ r_M$

• $1\le N \le 300$
• $0\le M \le min(300,\frac{N(N+1)}{2})$
• $0\le X,\ A_i \le 10^9$
• $type_i\ =\ 0,\ 1$
• $1 \le l_i \le r_i\le N$
• If $i \neq j$, then $(l_i,\ r_i)\neq (l_j,\ r_j)$
• All input values are integers

Output

Print on one line the number of ways to choose integers satisfying the conditions, modulo $10^9+7$.

Sample

4 2 3
1 1 2 2
0 2 3
0 1 4

2

4 1 3
1 1 2 2
1 1 4

0

7 3 2
1 2 3 4 5 6 7
0 2 4
0 5 6
1 2 6

0

15 5 12582921
12582923 10485775 5242888 9437185 3145743 10485768 13631489 2097158 11534339 15 14680065 6291461 7340039 10485764 7340035
1 4 11
0 5 6
0 13 15
0 1 10
0 8 11

8