说明

时间限制：1 Sec 内存限制：256 MB 输入文件：xor.in 输出文件：xor.out

小明有一个长度为 $N$ 的整数序列 $A_1,A_2,\dots,A_N$ 和一个整数 $X$。

他思考了这样一个问题：

> 从 $A_1,A_2,\dots,A_N$ 中选出 $0$ 个或多个元素，计算所选元素的按位异或和。请问有多少种选法，能让计算结果恰好等于 $X$？

由于小明非常喜欢按位异或运算，他觉得这个问题有些过于简单。于是他额外添加了 $M$ 条约束条件，每条条件都属于以下两种形式之一：

- 类型 $0$ $0\ l\ r$：从子序列 $A_l,A_{l+1},\dots,A_r$ 中选出的元素个数必须为偶数（选 $0$ 个也符合要求）。

- 类型 $1$ $1\ l\ r$：从子序列 $A_l,A_{l+1},\dots,A_r$ 中选出的元素个数必须为奇数。

请你计算：在满足全部 $M$ 条约束条件的前提下，选出若干元素使其按位异或和等于 $X$ 的选法总数，结果对 $10^9+7$ 取模后输出。

补充说明：当不选任何元素时，规定其按位异或和为 $0$。

输入格式

第一行三个整数 $N,M,X$。

第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。

接下去 $M$ 行，第 $i$ 行三个整数 $type_i,l_i,r_i$ 表示一个约束条件，含义如题面描述。

输出格式

输出一行，包含满足所有条件的选法总数对 $10^9+7$ 取模后的结果。

样例

样例 1

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

2

样例说明：

满足所有条件的选法共有 $2$ 种，分别是选取 $\{a_1,a_4\}$ 和 $\{a_2,a_3\}$。

样例 2

4 1 3
1 1 2 2
1 1 4

0

样例说明：

从整个序列中选取奇数个元素时，无法得到异或和为 $3$ 的结果。

样例 3

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

0

样例 4

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

数据范围

对于 20% 的数据，满足 $N \le 20$，$M \le \min(20,\frac{N(N+1)}{2})$。

对于 100% 的数据，满足 $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 \in \{0,1\}$，$1 \le l_i \le r_i\le N$，若 $i \neq j$，则 $(l_i,\ r_i)\neq (l_j,\ r_j)$。