BZPRO
#3746. [POI2015]Czarnoksiężnicy okrągłego stołu
内存限制：128 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
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。
数据范围与提示
BZPRO