問題文

henoくんは長さ$N$の整数列$A_1,\ A_2,\cdots ,\ A_N$と整数$X$を持っています。 henoくんは以下の問題を考えていました。

「$A_1,\ A_2,\cdots ,A_N$の中から0個以上を選んで、選んだすべての整数のビットごとの排他的論理和を計算する。 計算結果が$X$となるような整数の選び方は何通りあるか？」

henoくんは排他的論理和が大好きなのでこの問題は少し簡単すぎました。そこでさらに以下の形式のいずれかで表される 条件を$M$個加えることにしました。

• $0\ l\ r\ $: $A_l,\ A_{l+1},\cdots ,\ A_r$の中から選ぶ個数は偶数個(0個でもよい)。
• $1\ l\ r\ $: $A_l,\ A_{l+1},\cdots ,\ A_r$の中から選ぶ個数は奇数個。

入力

$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$
• $i \neq j$ならば$(l_i,\ r_i)\neq (l_j,\ r_j)$
• 与えられる入力はすべて整数

出力

条件をみたす整数の選び方の個数を$10^9+7$で割った余りを1行に出力してください。

サンプル

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