Olya and Graph

题意翻译

Olya现在有一张n个点、m条边的有向无权图。现在我们以某种方式给所有点从1到n标号，从而保证原图中任意从u到v的有向边满足不等式：u<v。 　　现在Olya想知道有多少种方案添加任意数量（可能是0）的有向边，使得该图满足下列条件： 　　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的边，而第二张图中没有。 　　帮助Olya。由于要求的答案可能太大，将答案对1000000007取模后输出。

题目描述

Olya has got a directed non-weighted graph, consisting of $ n $ vertexes and $ m $ edges. We will consider that the graph vertexes are indexed from 1 to $ n $ in some manner. Then for any graph edge that goes from vertex $ v $ to vertex $ u $ the following inequation holds: $ v&lt;u $ . Now Olya wonders, how many ways there are to add an arbitrary (possibly zero) number of edges to the graph so as the following conditions were met: 1. You can reach vertexes number $ i+1,i+2,...,n $ from any vertex number $ i $ $ (i&lt;n) $ . 2. For any graph edge going from vertex $ v $ to vertex $ u $ the following inequation fulfills: $ v&lt;u $ . 3. There is at most one edge between any two vertexes. 4. The shortest distance between the pair of vertexes $ i,j $ $ (i&lt;j) $ , for which $ j-i<=k $ holds, equals $ j-i $ edges. 5. The shortest distance between the pair of vertexes $ i,j $ $ (i&lt;j) $ , for which $ j-i&gt;k $ holds, equals either $ j-i $ or $ j-i-k $ edges. We will consider two ways distinct, if there is the pair of vertexes $ i,j $ $ (i&lt;j) $ , such that first resulting graph has an edge from $ i $ to $ j $ and the second one doesn't have it. Help Olya. As the required number of ways can be rather large, print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains three space-separated integers $ n,m,k $ $ (2<=n<=10^{6},0<=m<=10^{5},1<=k<=10^{6}) $ . The next $ m $ lines contain the description of the edges of the initial graph. The $ i $ -th line contains a pair of space-separated integers $ u_{i},v_{i} $ $ (1<=u_{i}&lt;v_{i}<=n) $ — the numbers of vertexes that have a directed edge from $ u_{i} $ to $ v_{i} $ between them. It is guaranteed that any pair of vertexes $ u_{i},v_{i} $ has at most one edge between them. It also is guaranteed that the graph edges are given in the order of non-decreasing $ u_{i} $ . If there are multiple edges going from vertex $ u_{i} $ , then it is guaranteed that these edges are given in the order of increasing $ v_{i} $ .

输出格式

Print a single integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

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

输出样例 #1

2

输入样例 #2

7 0 2

输出样例 #2

12

输入样例 #3

7 2 1
1 3
3 5

输出样例 #3

0

说明

In the first sample there are two ways: the first way is not to add anything, the second way is to add a single edge from vertex $ 2 $ to vertex $ 5 $ .