Problem 1. Cow Poetry

USACO 2019 January Contest, Gold

不为Farmer John所知的是，Bessie还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。

Bessie认识$N$（$1 \leq N \leq 5000$）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。

Bessie的每首诗由$M$行组成（$1 \leq M \leq 10^5$），每一行必须由$K$（$1 \leq K \leq 5000$）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。

Bessie想要知道她可以写出多少首符合限制条件的不同的诗。

输入格式（文件名：poetry.in）：

输入的第一行包含$N$、$M$和$K$。

以下$N$行，每行包含两个整数$s_i$（$1 \leq s_i \leq K$）和$c_i$（$1 \leq c_i \leq N$）。这表示Bessie认识一个长度（以音节为单位）为$s_i$、属于韵部$c_i$的单词。

最后$M$行描述了Bessie想要的押韵模式，每行包含一个大写字母$e_i$。所有押韵模式等于$e_i$的行必须以同一韵部的单词结尾。不同$e_i$值的行并非必须以不同的韵部的单词结尾。

输出格式（文件名：poetry.out）：

输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。

输入样例：

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

输出样例：

960

在这个例子中，Bessie认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗（其中1，2、3分别代表第一个、第二个、第三个单词）：121 123 321。

供题：Jay Leeds