Description

n个人（编号为1~n）围着圆桌坐成一圈。座位相邻的两个人，其编号之差的绝对值不可以超过p。

他们之中有些人不喜欢别人。如果a不喜欢b，那么b不能坐在a右边的那一个位置上。

现在，假设第n个人的座位已经固定，要给剩下的人安排座位，共有几种合法方案？

Format

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后的值。

Samples

5 2 3
1 3
5 4

6

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

Limitation