题目背景

做化学反应的时候记得小心打火机，出题人已经被烫到好几次了。

题目描述

小 Q 的化学实验室中有 $n$ 种试剂，编号为 $1\sim n$，小 Q 想把它们按某种特定的顺序排成一圈。

为了方便记忆，小 Q 想要将能发生反应的两种试剂放在相邻的位置上，或者说任意两个相邻的药剂都要能发生反应。

由于小 Q 的化学试剂比较特殊，所以两个编号为 $x,y$ 的试剂能发生反应的必要条件是 $-k\le x-y\le k$。

另外，由于化学总是有很多特例，所以还存在 $m$ 对关系 $(a,b)$ 表示试剂 $a$ 的顺时针下一个位置不能是试剂 $b$（但是 $b$ 下一个是 $a$ 是可以的，除非还有一对关系 $(b,a)$），不然可能因为宇宙射线导致实验室发生爆炸，这是小 Q 不想看到的。

请你帮助她求出，存在多少种不同的排列这些药剂的方式，使得满足以上所有条件？

注意，如果两种排列轮换后相同，我们视为同一种，比如 $(1,2,3)=(3,1,2)=(2,3,1)$。但 $(1,2,3)\ne(1,3,2)$。

答案对 $10^9+7$ 取模。

输入格式

第一行三个整数 $n,m,k$，表示试剂数，关系数与用于判定必要条件的特定常量。

接下来 $m$ 行，每行两个正整数 $a,b$，表示一对关系 $(a,b)$。

输出格式

输出一个整数，表示满足条件的排列数量对 $10^9+7$ 取模的结果。

样例 1 输入

3 1 2
1 2

样例 1 输出

1

样例 1 解释

仅有 $(2,1,3)$ 及其轮换合法。

样例 2 输入

6 5 3
2 3
1 4
3 5

样例 2 输出

11

样例 3

见选手目录下的 $\boldsymbol{chemical/chemical3.in}$ 与 $\boldsymbol{chemical/chemical3.ans}$。

该样例满足子任务 $2$ 的限制。

样例 4

见选手目录下的 $\boldsymbol{chemical/chemical4.in}$ 与 $\boldsymbol{chemical/chemical4.ans}$。

该样例满足子任务 $5$ 的限制。

样例 5

见选手目录下的 $\boldsymbol{chemical/chemical5.in}$ 与 $\boldsymbol{chemical/chemical5.ans}$。

该样例满足子任务 $6$ 的限制。

样例 6

见选手目录下的 $\boldsymbol{chemical/chemical6.in}$ 与 $\boldsymbol{chemical/chemical6.ans}$。

该样例满足子任务 $7$ 的限制。

样例 7

见选手目录下的 $\boldsymbol{chemical/chemical7.in}$ 与 $\boldsymbol{chemical/chemical7.ans}$。

该样例满足子任务 $9$ 的限制。

数据范围

本题使用子任务（Subtask）计分。你需要通过一个子任务内所有测试数据才可以获得相应的得分。

对于所有测试数据，保证：

• $1\le n\le1000$；
• $0\le m\le 2\times10^5$；
• $1\le k\le 6$；
• $1\le a_i \ne b_i\le n$。

特殊性质 A：保证 $m=0$。