题目描述

译自 ROI Regional 2019 Day1 T4. Машинное обучение

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

训练集的复杂度从 $0$ 到 $k$ 不等。训练计划由一个整数数组 $[a_{1}, a_{2}, \ldots, a_{n}]$ 表示，其中 $a_{i}$ 表示第 $i$ 次迭代中使用的训练集的复杂度。对于所有 $i$ 从 $1$ 到 $n$，必须满足 $0 \leq a_{i} \leq k$。

研究发现，训练计划的有效性取决于训练集复杂度的位表示。为了使计划有效，必须满足对于任意两个值 $i$ 和 $j$，其中 $1 \leq i < j \leq n$，都有 $(a_{i} \operatorname{and} a_{j})=a_{i}$。回顾一下，两个非负整数的按位与（and）操作如下：将两个数写成二进制形式，如果两个数的第 $i$ 位都是 $1$，则结果的第 $i$ 位为 $1$。例如，$(14 \operatorname{and} 7)=(1110_{2} \operatorname{and} 0111_{2})=110_{2}=6$。

然而，持续使用相同复杂度的训练集不会带来学习进展。为了避免这种情况，训练计划必须满足 $m$ 个要求。每个要求由两个数字 $l_{i}$ 和 $r_{i}$ 表示，意味着 $a_{l_{i}} \neq a_{r_{i}}$。

实验室的工作人员希望找到满足所有要求的有效计划的数量。由于这个数量可能非常大，需要计算它除以 $10^{9}+7$ 的余数。

编写一个程序，根据给定的整数 $n$ 和 $k$，以及 $m$ 个要求 $l_{i}, r_{i}$，确定满足所有要求的有效计划的数量，并输出这个数量除以 $10^{9}+7$ 的余数。

输入格式

第一行输入包含三个整数 $n$, $m$, $k$ $(1 \leq n \leq 3 \cdot 10^{5}, 0 \leq m \leq 3 \cdot 10^{5}, 0 \leq k \leq 10^{18})$，分别表示训练迭代次数、要求数量和训练集的最大复杂度。

接下来的 $m$ 行描述了要求，第 $i$ 行包含两个整数 $l_{i}, r_{i}$ $(1 \leq l_{i} < r_{i} \leq n)$，表示 $a_{l_{i}} \neq a_{r_{i}}$。保证所有要求都是不同的。

输出格式

输出一个整数，表示满足所有要求的有效计划的数量除以 $10^{9}+7$ 的余数。

样例 1

输入

2 0 3

输出

9

第一个样例的所有可能计划：$[0,0],[0,1],[0,2],[0,3],[1,1],[1,3],[2,2],[2,3],[3,3]$。

样例 2

输入

3 1 2
1 2

输出

2

第二个样例的可能计划：$[0,1,1],[0,2,2]$。

数据范围与提示

详细子任务附加限制及分值如下表所示。