题目描述

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<h_i\le 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

10 1 20
1 3

399988086

提示

样例解释 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 2000$。
• 测试点 $16-20$：没有额外限制。