主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 B: 余神的图

问题 B: 余神的图

时间限制: 1 Sec  内存限制: 256 MB
提交: 2  解决: 2
[提交][状态][讨论版]

题目描述

余神有一张n 个点、m 条边的有向无权图,所有点从1 到n 标号。
现在余神 想知道有多少种添加有向边的方案(可不添加),使得该图满足下列条件:
     1、从点i 出发,可以到达点i+1,i+2,…..,n。
     2、任意从u 到v 的有向边满足不等式:u<v。
     3、两点之间最多有一条边。
     4、对于一对点i、j(i<j),若j-i<=k,那么从i 到j 的最短距离等于j-i。
     5、对于一对点i、j(i<j),若j-i>k,那么从i 到j 的最短距离等于j-i 或j-i-k。

我们认为两种添加边的方案不同,当且仅当存在至少一对点i、j(i<j),一张图中有一条从i 连向j 的边,而另一张图中没有。
帮助余神!

由于要求的答案可能太大,将答案对1000000007 取模后输出。

输入

第一行包含三个用空格隔开的整数,n,m,k。接下来m 行描述原图的有向边。

第i 行包含一对用空格隔开的整数ui,vi,表示第i 条有向边从ui 连向vi。

输出

输出一个整数,即答案模1000000007。

样例输入

7 8 2
1 2
2 3
3 4
3 6
4 5
4 7
5 6
6 7

样例输出

2

提示

单组数据,保证输入中任意一对点ui,vi 之间最多有一条边。


并且保证输入中给出的ui 不下降。


如果有多条有向边从ui 出发,那么这些边将按照vi 升序给出。


保证原图中任意从u 到v的有向边满足不等式:u<v。


对于100%的数据,2<=n<=10^6,0<=m<=10^5,1<=k<=10^6。

[提交][状态][讨论版]