P10138 [USACO24JAN] Cowmpetency G

Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2\le N\le 10^9$）头奶牛来担任该职位。在每次面试后，他会为候选牛分配一个 $1$ 到 $C$（$1\le C\le 10^4$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。 由于 Farmer John 面试了如此多的奶牛，他已经忘记了所有奶牛的牲任力分数。然而，他确实记得 $Q$ （$1\le Q\le \min(N-1,100)$）对数字 $(a_i,h_i)$，其中奶牛 $h_i$ 是第一头比奶牛 $1$ 到 $a_i$ 拥有**严格**更高牲任力分数的奶牛（所以 $1\le a_i

输入的第一行包含 $N$，$Q$ 和 $C$。 以下 $Q$ 行，每行包含一个数对 $(a_i,h_i)$。输入保证所有 $a_i$ 各不相同。

输出与 Farmer John 记忆一致的牲任力分数序列的数量，对 $10^9+7$ 取模。

### 样例解释 1 以下六个序列是仅有的与 Farmer John 记忆一致的序列： $1\ 1\ 2\ 1\ 3\ 1$ $1\ 1\ 2\ 1\ 3\ 2$ $1\ 1\ 2\ 1\ 3\ 3$ $1\ 1\ 2\ 2\ 3\ 1$ $1\ 1\ 2\ 2\ 3\ 2$ $1\ 1\ 2\ 2\ 3\ 3$ ### 样例解释 2 确保输出答案对 $10^9+7$ 取模。 ### 测试点性质 - 测试点 $3-4$：$N\le 10$ 且 $Q,C\le 4$。 - 测试点 $5-7$：$N,C\le 100$。 - 测试点 $8-10$：$N\le 2000$ 且 $C\le 200$。 - 测试点 $11-15$：$N,C\le 5000$。 - 测试点 $16-20$：没有额外限制。