[POI2015]Czarnoksieznicy okraglego stolu

时间限制:10s      空间限制:128MB

题目描述

n个人(编号为1~n)围着圆桌坐成一圈。座位相邻的两个人,其编号之差的绝对值不可以超过p。
他们之中有些人不喜欢别人。如果a不喜欢b,那么b不能坐在a右边的那一个位置上。
现在,假设第n个人的座位已经固定,要给剩下的人安排座位,共有几种合法方案?


输入格式

第一行包含三个整数n,k,p(1<=n<=1000000,0<=k<=100000,0<=p<=3)。
接下来k行,每行含两个整数a[i],b[i](1 <= a[i],b[i] <= n, a[i]≠b[i]),表示a[i]不喜欢b[i]。同一组a[i],b[i]不会重复输入。


输出格式

输出一个整数,表示方案数模10^9+7后的值。


样例输入

5 2 3
1 3
5 4

样例输出

6

样例解释:
合法方案有53124,53142,52143,53412,52314,53214。

提示

没有写明提示


题目来源

鸣谢Jcvb