题目背景

翻译自 ROIR 2019 D1T4。

题目描述

有一种新的机器学习方法。在训练过程中，程序会进行 $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$ 取模的结果。

2 0 3

9

3 1 2
1 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]$。

数据范围

数据中 Subtask 0 为样例。