CF305D Olya and Graph

Olya 有一个由 $n$ 个顶点和 $m$ 条边组成的有向无权图。我们假设图的顶点按照某种方式从 $1$ 到 $n$ 编号。对于每一条从顶点 $v$ 指向顶点 $u$ 的有向边，都满足不等式 $v < u$。 现在 Olya 想知道，有多少种方式在该图中添加任意数量（可以为零）的边，使得同时满足以下条件： 1. 对于任意 $i < n$，都可以从编号为 $i$ 的顶点到达所有编号为 $i+1,i+2,\ldots,n$ 的顶点。 2. 对于每一条从顶点 $v$ 指向顶点 $u$ 的有向边，都要满足不等式 $v < u$。 3. 任意两顶点之间至多只有一条边。 4. 对于任意满足 $i < j$ 且 $j-i \leq k$ 的顶点对 $(i,j)$，它们之间的最短距离等于 $j-i$ 条边。 5. 对于任意满足 $i < j$ 且 $j-i > k$ 的顶点对 $(i,j)$，它们之间的最短距离等于 $j-i$ 或 $j-i-k$ 条边。 我们认为两种方式不同，即存在顶点对 $(i,j)$，使得第一种方式生成的图中存在从 $i$ 到 $j$ 的边，而在第二种方式生成的图中不存在这条边。 请帮助 Olya 计算方案总数。由于答案可能很大，请输出对 $1000000007$（$10^9+7$）取模后的结果。

第一行包含三个用空格分隔的整数 $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}$ 递增顺序给出。

输出一个整数，表示方案数对 $1000000007$（$10^9+7$）取模的结果。

在第一个样例中，有两种方式：第一种方式是什么也不添加，第二种方式是从顶点 $2$ 到顶点 $5$ 添加一条边。 由 ChatGPT 5 翻译