← 返回题目列表

Codeforces · 305/D

D. 奥莉亚和图谱

中文机器翻译题面 查看原题

Olya 得到了一个有向非加权图,由 n 个顶点和 m 个边组成。我们将考虑图顶点以某种方式从 1 到 n 进行索引。那么对于从顶点 v 到顶点 u 的任何图边,以下不等式成立:v < u。

现在 Olya 想知道,有多少种方法可以向图中添加任意(可能为零)数量的边,以满足以下条件:

1. 从任意顶点 i (i < n) 可以到达顶点 i + 1, i + 2, ..., n。
2. 对于从顶点 v 到顶点 u 的任何图边,满足以下不等式:v < u。
3. 任意两个顶点之间至多有一条边。
4. j - i ≤ k 成立的一对顶点 i, j (i < j) 之间的最短距离等于 j - i 边。
5. j - i > k 成立的顶点对 i, j (i < j) 之间的最短距离等于 j - i 或 j - i - k 边。

如果存在一对顶点 i, j (i < j),我们将考虑两种不同的方式,使得第一个结果图具有从 i 到 j 的边,而第二个结果图没有它。

帮助奥莉亚。由于所需的路数可能相当大,因此打印模 1000000007 (109 + 7)。

输入

第一行包含三个空格分隔的整数 n、m、k (2 ≤ n ≤ 106, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106)。

接下来的 m 行包含初始图的边的描述。第 i 行包含一对空格分隔的整数 ui, vi (1 ≤ ui < vi ≤ n) — 之间具有从 ui 到 vi 的有向边的顶点数。

保证任何一对顶点 ui, vi 之间最多有一条边。还保证图的边按照 ui 非递减的顺序给出。如果有多条从顶点 ui 出发的边,则保证这些边按 vi 递增的顺序给出。

输出

打印一个整数——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

7 8 2
1 2
2 3
3 4
3 6
4 5
4 7
5 6
6 7

输出 #1

2

输入 #2

7 0 2

输出 #2

12

输入 #3

7 2 1
1 3
3 5

输出 #3

0

注意

在第一个示例中,有两种方法:第一种方法是不添加任何内容,第二种方法是添加从顶点 2 到顶点 5 的单条边。