Cowmpetency

题目描述

农夫约翰正在为他的奶牛招聘一位新的牛群领袖。为此，他面试了 $N$（$2 \leq N \leq 10^9$）头奶牛。每次面试结束后，他都会给候选者分配一个整数“cowmpetency（牛力）”评分，范围从 $1$ 到 $C$（$1 \leq C \leq 10^4$），该评分与她们的领导能力相关。

由于他面试了太多奶牛，农夫约翰已经忘记了所有奶牛的 cowmpetency 分数。不过，他还记得 $Q$（$1 \leq Q \leq \min(N - 1, 100)$）对数 $(a_i, h_i)$：其中奶牛 $h_i$ 是第一头 cowmpetency 分数严格大于第 $1$ 头到第 $a_i$ 头奶牛的奶牛（因此 $1 \leq a_i < h_i \leq N$）。

现在农夫约翰把这 $Q$ 对 $(a_i, h_i)$ 告诉你。请帮助他统计有多少个 cowmpetency 分数序列与这些信息一致！保证至少存在一个这样的序列。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含 $N$、$Q$ 和 $C$。 接下来 $Q$ 行每行包含一对 $(a_i, h_i)$。保证所有 $a_j$ 互不相同。

输出格式

输出与农夫约翰记忆一致的 cowmpetency 分数序列数量，对 $10^9+7$ 取模。

6 2 3
2 3
4 5

6

10 1 20
1 3

399988086

提示

以下六个序列是与农夫约翰记忆一致的仅有序列： 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^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

标签: USACO|2024|Gold

来源

USACO|2024|Gold