人工智能实验室开发了一种新的机器学习方法。训练程序需要进行 $n$ 次迭代。每次迭代中，程序会在某个训练集上运行。

训练集的复杂度从 $0$ 到 $k$。一个训练计划由整数数组

$$[a_1,a_2,\ldots,a_n]$$

描述，其中 $a_i$ 表示第 $i$ 次迭代使用的训练集复杂度。对所有 $i$，必须满足：

$$0\le a_i\le k.$$

研究人员发现，训练计划的效果与复杂度的二进制表示有关。为了使计划有效，需要对任意 $1\le i<j\le n$，满足：

$$(a_i\ \text{and}\ a_j)=a_i.$$

这里 and 表示按位与。例如：

$$14\ \text{and}\ 7=(1110_2\ \text{and}\ 0111_2)=0110_2=6.$$

在 C++、Java 和 Python 中，该操作记为 &。

但是，一直使用同一复杂度的训练集无法取得进步。因此训练计划还必须满足 $m$ 个额外要求。每个要求由两个整数 $l_i,r_i$ 给出，表示：

$$a_{l_i}\ne a_{r_i}.$$

请计算有多少个有效训练计划满足所有这些要求。答案可能很大，请输出它对 $10^9+7$ 取模后的结果。

输入格式

第一行包含三个整数：

$$n,\ m,\ k$$

其中：

$$1\le n\le 3\cdot 10^5,\qquad 0\le m\le 3\cdot 10^5,\qquad 0\le k\le 10^{18}.$$

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$，表示要求 $a_{l_i}\ne a_{r_i}$：

$$1\le l_i<r_i\le n.$$

保证所有要求互不相同。

输出格式

输出一个整数：满足条件的有效训练计划数量对 $10^9+7$ 取模的结果。

样例 1 输入

2 0 3

样例 1 输出

9

样例 2 输入

3 1 2
1 2

样例 2 输出

2

样例说明

样例 1 中所有可能的训练计划为：

$$[0,0],\ [0,1],\ [0,2],\ [0,3],\ [1,1],\ [1,3],\ [2,2],\ [2,3],\ [3,3].$$

样例 2 中满足条件的计划为：

$$[0,1,1],\ [0,2,2].$$

子任务

子任务	分值	限制	依赖	检查信息
1	8	$1\le n\le 500,\ m=0,\ 0\le k\le 500$	-	完全反馈
2	20	$1\le n\le 3\cdot 10^5,\ m=0,\ 0\le k\le 10^7$	1	第一错误
3	10	$1\le n\le 3\cdot 10^5,\ m=0,\ 0\le k\le 10^{18}$	1, 2
4	8	$1\le n\le 50,\ 0\le m\le 50,\ 0\le k\le 50$	-
5	16	$1\le n\le 2000,\ 0\le m\le 2000,\ 0\le k\le 10^7$	1, 4
6		$1\le n\le 2000,\ 0\le m\le 2000,\ 0\le k\le 10^{18}$	1, 4, 5
7	10	$1\le n\le 3\cdot 10^5,\ 0\le m\le 200,\ 0\le k\le 10^7$	1, 2, 4
8	6	$1\le n\le 3\cdot 10^5,\ 0\le m\le 200,\ 0\le k\le 10^{18}$	1, 2, 3, 4, 7
9	16	$1\le n\le 3\cdot 10^5,\ 0\le m\le 3\cdot 10^5,\ 0\le k\le 10^{18}$	1-8