时间限制：1秒　　内存限制：256M

---

【问题描述】

　　不为农夫约翰所知的是，贝西还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。
　　贝西认识 \(N\) 个单词，她想要将她们写进她的诗。贝西已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
　　贝西的每首诗由 \(M\) 行组成，每一行必须由 \(K\) 个音节构成。此外，贝西的诗必须遵循某个指定的押韵模式。
　　贝西想要知道她可以写出多少首符合限制条件的不同的诗。

【输入格式】

　　输入的第一行包含 \(N、M\) 和 \(K\)。
　　以下 \(N\) 行，每行包含两个整数 \(s_i(1≤s_i≤K)\) 和 \(c_i(1≤c_i≤N)\)。这表示贝西认识一个长度（以音节为单位）为 \(s_i\)、属于韵部 \(c_i\) 的单词。
　　最后 \(M\) 行描述了贝西想要的押韵模式，每行包含一个大写字母 \(e_i\)。所有押韵模式等于 \(e_i\) 的行必须以同一韵部的单词结尾。不同 \(e_i\) 值的行并非必须以不同的韵部的单词结尾。

【输出格式】

　　输出贝西可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对 \(10^9+7\) 取余的结果。

【输入输出样例】

　Input

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

　Output

960

【输入输出样例解释】

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

【数据限制】

　　\(100\%\) 的数据满足：\(1≤N≤5000\) ，\(1≤M≤10^5\)，\(1≤K≤5000\)。

【来源】

　　Mr.he