题目描述

题目译自 XXII Olimpiada Informatyczna — I etap Czarnoksiężnicy okrągłego stołu

圆桌巫师们再次举行秘密会议，却又为座位顺序争执不下。会议有 $n$ 位巫师，每人戴着高度独特的尖帽，高度为 $1$ 到 $n$ 的不同整数（帽越高，资历越深）。为保持圆桌美观，相邻巫师的帽高差不能超过 $p$。

此外，巫师之间有些不和：若巫师 $a$ 不喜欢巫师 $b$，则 $b$ 不能坐在 $a$ 的右侧。会议主席（帽高为 $n$）已选定座位。请你计算其他巫师加入座位的可能排列方式有多少种。

输入格式

输入第一行包含三个整数 $n, k, p$ $(1 \leq n \leq 1000000, 0 \leq k \leq 100000, 0 \leq p \leq 3)$，分别表示巫师人数、不喜欢关系的数量和帽高最大差值。

接下来的 $k$ 行，每行两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示帽高为 $a_{i}$ 的巫师不喜欢帽高为 $b_{i}$ 的巫师。每对有序巫师对最多出现一次。

输出格式

输出一行一个整数，表示排列方式数对 $10^{9}+7$ 取模的结果。

5 2 3
1 3
5 4

6

巫师可按以下六种方式围坐圆桌：$53124$、$53142$、$52143$、$53412$、$52314$、$53214$。

附加样例

1. 小型样例，其中存在某巫师无人不喜欢；
2. $n=5, k=0, p=3$；
3. $n=1000000, k=0, p=2$。

数据范围与提示

对于 $16\%$ 的数据，$n \leq 5$。
对于另外 $16\%$ 的数据，$p \leq 2$。