P11498 [ROIR 2019] 机器学习 (Day 1)

翻译自 [ROIR 2019 D1T4](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-regional-2019-day1.pdf)。

有一种新的机器学习方法。在训练过程中，程序会进行 $n$ 次迭代。每次迭代中，训练程序会在某个训练集上运行。 训练集的复杂度从 $0$ 到 $k$ 不等。训练计划由一个整数数组 $[a_{1}, a_{2}, \dots, a_{n}]$ 表示，其中 $0 \leq a_{i} \leq k$，$a_{i}$ 表示第 $i$ 次迭代中使用的训练集的复杂度。 研究发现，训练计划的有效性取决于训练集复杂度的二进制表示。为了使计划有效，必须满足对于任意的 $1 \leq i < j \leq n$，都有 $(a_{i} \operatorname{and} a_{j})=a_{i}$，其中 $\operatorname{and}$ 是按位与。 然而，持续使用相同复杂度的训练集不会带来学习进展。为了避免这种情况，训练计划必须满足 $m$ 个二元限制。每个二元限制由两个数字 $l_{i}$ 和 $r_{i}$ 表示，意味着 $a_{l_{i}} \neq a_{r_{i}}$。 实验室的工作人员希望找到满足所有二元限制的有效计划的数量。由于答案可能很大，你只需要求出答案对 $10^{9}+7$ 取模后的值。

第一行输入三个整数 $n, m, k$，分别表示训练迭代次数、二元限制的数量和训练集的最大复杂度。 接下来 $m$ 行，每行输入一个二元限制。其中第 $i$ 行输入两个整数 $l_{i}, r_{i}$，表示 $a_{l_{i}} \neq a_{r_{i}}$。保证所有二元限制都是不同的。

输出一个整数，表示满足所有二元限制的有效计划的数量对 $10^{9}+7$ 取模的结果。

### 样例解释 样例 $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]$。 ### 数据范围 数据中 Subtask 0 为样例。 | 子任务 | 分值 | $1\le n\le$ | $0\le m\le$ | $0\le k\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $8$ | $500$ | $0$ | $500$ | | $2$ | $20$ | $3\times10^5$ | $0$ | $10^7$ | | $3$ | $10$ | $3\times10^5$ | $0$ | $10^{18}$ | | $4$ | $8$ | $50$ | $50$ | $50$ | | $5$ | $16$ | $2000$ | $2000$ | $10^7$ | | $6$ | $6$ | $2000$ | $2000$ | $10^{18}$ | | $7$ | $10$ | $3\times10^5$ | $200$ | $10^7$ | | $8$ | $6$ | $3\times10^5$ | $200$ | $10^{18}$ | | $9$ | $16$ | $3\times10^5$ | $3\times10^5$ | $10^{18}$ |