Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 07:31:47 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|