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

题目描述

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。  

数据范围与提示