题目描述

请注意 $L$ 的范围！

给定两个正整数 $n,L$ 和 $m$ 个有序二元组 $(a_i,b_i)\ (1\le a_i,b_i\le n)$，计数满足以下性质的排列 $p$ 数量：

• $p_1=1$；
• $\lvert p_i - p_{(i\bmod n)+1}\rvert \le L$；
• $\forall i,j$，$p_i\ne a_j\ \lor\ p_{(i\bmod n)+1}\ne b_j$。

由于结果可能很大，输出时对 $10^9+7$ 取模。

输入格式

第 1 行三个正整数 $n,m,L$。
接下来 $m$ 行每行两个正整数 $a_i,b_i$。

输出格式

输出一个正整数，表示合法排列个数对 $10^9+7$ 取模的结果。

5 2 3
1 3
5 4

6

数据范围与提示

• 对于 10% 的数据：$n\le 10$；
• 对于另外 10% 的数据：$L\le 2$；
• 对于另外 30% 的数据：$m=0$；
• 对于 100% 的数据：$1\le n\le 10^6$，$0\le m\le 10^5$，$0\le L\le 3$。