UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3746. [POI2015]Czarnoksiężnicy okrągłego stołu

统计 下载数据

Description

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

Input

第一行包含三个整数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]不会重复输入。

Output

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

Sample Input

5 2 3
1 3
5 4

Sample Output

6

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

Hint

Source

鸣谢Jcvb