No tag edit access

D. Olya and Graph

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOlya 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).

Input

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}.

Output

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

Examples

Input

7 8 2

1 2

2 3

3 4

3 6

4 5

4 7

5 6

6 7

Output

2

Input

7 0 2

Output

12

Input

7 2 1

1 3

3 5

Output

0

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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2017 16:52:52 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|