Olya and Graph

2000ms

262144K

Description:

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⁹ + 7).

Input:

The first line contains three space-separated integers n, m, k (2 ≤ n ≤ 10⁶, 0 ≤ m ≤ 10⁵, 1 ≤ k ≤ 10⁶).

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.

Output:

Print a single integer — the answer to the problem modulo 1000000007 (10⁹ + 7).

Sample Input:

Sample Output:

Sample Input:

7 0 2

Sample Output:

Sample Input:

7 2 1
1 3
3 5

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF305D