Cow Poetry

题目描述

农夫约翰并不知道，贝茜其实非常热爱艺术！最近，她开始研读许多伟大的诗人，现在她想尝试自己写诗。 贝茜知道 $N$（$1 \leq N \leq 5000$）个单词，并希望将它们排列成诗。贝茜已经确定了每个单词的音节数，并且把它们分配到若干“押韵类别”中。每个单词只与同一押韵类别中的其他单词押韵。 贝茜的每首诗包含 $M$ 行（$1 \leq M \leq 10^5$），并且每一行必须由恰好 $K$（$1 \leq K \leq 5000$）个音节组成。此外，贝茜的诗必须遵循一个特定的押韵方案。 贝茜想知道，在满足给定约束的情况下，她可以写出多少种不同的诗。

输入格式

第一行输入包含 $N$、$M$ 和 $K$。 接下来的 $N$ 行输入每行包含两个数 $s_i$（$1 \leq s_i \leq K$）和 $c_i$（$1 \leq c_i \leq N$）。这表示贝茜知道一个音节长度为 $s_i$、押韵类别为 $c_i$ 的单词。 最后 $M$ 行输入描述贝茜期望的押韵方案，每行包含一个大写字母 $e_i$。所有对应相同 $e_i$ 的行必须以同一押韵类别的单词结尾。对应不同 $e_i$ 的行不一定要以不同押韵类别的单词结尾。

输出格式

输出贝茜在满足这些约束的情况下可以写出的诗的数量。 由于该数量可能非常大，请输出对 1,000,000,007 取模后的结果。

3 3 10
3 1
4 1
3 2
A
B
A

960

提示

在这个例子中，贝茜知道三个单词。前两个单词押韵，长度分别为三个音节和四个音节；最后一个单词长度为三个音节，并且不与其他单词押韵。她想写一首三行的诗，使得每行包含十个音节，并且第一行与最后一行押韵。这样的诗共有 960 首。一个合法的诗的例子如下（其中 1、2、3 分别代表第一个、第二个和第三个单词）：121 123 321 题目致谢：Jay Leeds

标签: USACO|2019|Gold

来源

USACO|2019|Gold