CF305D.Olya and Graph

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 (109 + 7).

奥莉娅得到了一个有向无权图，该图包含 $n$ 个顶点和 $m$ 条边。我们假定图中顶点按某种方式编号为 $1$ 到 $n$。对于图中任意一条从顶点 $v$ 指向顶点 $u$ 的边，均满足不等式：$v < u$。

现在奥莉娅想知道：有多少种方法可以向图中添加**任意数量（可能为零）**的新边，使得以下条件全部满足：

1. 对于任意顶点 $i$（其中 $i < n$），均可从顶点 $i$ 到达顶点 $i+1,\, i+2,\, \dots,\, n$；
2. 对于图中任意一条从顶点 $v$ 指向顶点 $u$ 的边，均满足不等式：$v < u$；
3. 任意两个顶点之间至多存在一条边；
4. 对于任意一对顶点 $i,\, j$（其中 $i < j$）且满足 $j - i \le k$，其最短距离（以边数计）恰好为 $j - i$；
5. 对于任意一对顶点 $i,\, j$（其中 $i < j$）且满足 $j - i > k$，其最短距离（以边数计）恰好为 $j - i$ 或 $j - i - k$。

若存在一对顶点 $i,\, j$（其中 $i < j$），使得第一个结果图中存在从 $i$ 到 $j$ 的边而第二个结果图中不存在，则认为这两种方案是不同的。

请帮助奥莉娅解决这个问题。由于所求方案数可能非常大，请将答案对 $1000000007$（即 $10^9 + 7$）取模后输出。

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

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.

第一行包含三个用空格分隔的整数 $n$、$m$、$k$（其中 $2 \leq n \leq 10^6$，$0 \leq m \leq 10^5$，$1 \leq k \leq 10^6$）。

接下来的 $m$ 行描述初始图的边。第 $i$ 行包含一对用空格分隔的整数 $u_i$、$v_i$（其中 $1 \leq u_i < v_i \leq n$），表示存在一条从顶点 $u_i$ 指向顶点 $v_i$ 的有向边。

保证任意一对顶点 $u_i$、$v_i$ 之间至多只有一条边。同时保证图中的边按 $u_i$ 非递减的顺序给出；若从同一顶点 $u_i$ 出发有多条边，则这些边按 $v_i$ 严格递增的顺序给出。

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

输出一个整数——该问题答案对 $1000000007$（即 $10^9 + 7$）取模的结果。

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.

在第一个样例中，有两种方式：第一种方式是不添加任何边；第二种方式是添加一条从顶点 2 到顶点 5 的单条边。