Problem 2. Cowmpetency

USACO 2024 January Contest, Gold

Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2 \leq N \leq 10^9$）头奶牛来担任该职位。在每次面试后，他会为候选牛分配一个 $1$ 到 $C$（$1 \leq C \leq 10^4$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。

由于 Farmer John 面试了如此多的奶牛，他已经忘记了所有奶牛的牲任力分数。然而，他确实记得 $Q$（$1 \leq Q \leq \min(N - 1, 100)$）对数字 $(a_i, h_i)$，其中奶牛 $h_i$ 是第一头比奶牛 $1$ 到 $a_i$ 拥有

严格更高

牲任力分数的奶牛（所以 $1 \leq a_i < h_i \leq N$）。

Farmer John 现在告诉你这 $Q$ 个数对 $(a_i, h_i)$。请帮助他数一下有多少个牲任力分数序列与此信息一致！输入保证存在至少一个这样的序列。由于这个数字可能非常大，输出该值模 $10^9 + 7$ 的余数。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$，$Q$ 和 $C$。

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

输出格式（输出至终端 / 标准输出）：

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

输入样例：

6 2 3
2 3
4 5

输出样例：

6

以下六个序列是仅有的与 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

输入样例：

10 1 20
1 3

输出样例：

399988086

确保输出答案对 $10^9+7$ 取模。

测试点性质： 测试点 3-4：$N \leq 10$ 且 $Q, C \leq 4$。测试点 5-7：$N, C \leq 100$。测试点 8-10：$N \leq 2000$ 且 $C \leq 200$。测试点 11-15：$N, C \leq 2000$。测试点 16-20：没有额外限制。

供题：Suhas Nagar