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:

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

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