{"raw_statement":[{"iden":"statement","content":"Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2\\le N\\le 10^9$）头奶牛来担任该职位。在每次面试后，他会为候选牛分配一个 $1$ 到 $C$（$1\\le C\\le 10^4$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。\n\n由于 Farmer John 面试了如此多的奶牛，他已经忘记了所有奶牛的牲任力分数。然而，他确实记得 $Q$\n（$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$）。\n\nFarmer John 现在告诉你这 $Q$ 个数对 $(a_i,h_i)$。请帮助他数一下有多少个牲任力分数序列与此信息一致！输入保证存在至少一个这样的序列。由于这个数字可能非常大，输出该值模 $10^9+7$ 的余数。"},{"iden":"input","content":"输入的第一行包含 $N$，$Q$ 和 $C$。\n\n以下 $Q$ 行，每行包含一个数对 $(a_i,h_i)$。输入保证所有 $a_i$ 各不相同。"},{"iden":"output","content":"输出与 Farmer John 记忆一致的牲任力分数序列的数量，对 $10^9+7$ 取模。"},{"iden":"note","content":"### 样例解释 1\n\n以下六个序列是仅有的与 Farmer John 记忆一致的序列：\n\n$1\\ 1\\ 2\\ 1\\ 3\\ 1$  \n$1\\ 1\\ 2\\ 1\\ 3\\ 2$  \n$1\\ 1\\ 2\\ 1\\ 3\\ 3$  \n$1\\ 1\\ 2\\ 2\\ 3\\ 1$  \n$1\\ 1\\ 2\\ 2\\ 3\\ 2$  \n$1\\ 1\\ 2\\ 2\\ 3\\ 3$  \n\n### 样例解释 2\n\n确保输出答案对 $10^9+7$ 取模。\n\n### 测试点性质\n\n- 测试点 $3-4$：$N\\le 10$ 且 $Q,C\\le 4$。\n- 测试点 $5-7$：$N,C\\le 100$。\n- 测试点 $8-10$：$N\\le 2000$ 且 $C\\le 200$。\n- 测试点 $11-15$：$N,C\\le 5000$。\n- 测试点 $16-20$：没有额外限制。"}],"translated_statement":null,"sample_group":[["6 2 3\n2 3\n4 5","6"],["10 1 20\n1 3","399988086"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}