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 < 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: You can reach vertexes number i + 1, i + 2, ..., n from any vertex number i ( i < n ) . For any graph edge going from vertex v to vertex u the following inequation fulfills: v < u . There is at most one edge between any two vertexes. The shortest distance between the pair of vertexes i , j ( i < j ) , for which j - i ≤ k holds, equals j - i edges. The shortest distance between the pair of vertexes i , j ( i < j ) , for which j - i > 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 < 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 < 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) . In the first sample there are two ways: the first way i