Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。
Bessie想要知道她可以写出多少首符合限制条件的不同的诗。
输入的第一行包含N、M和K。
以下N行，每行包含两个整数si（1≤si≤K）和ci（1≤ci≤N）。这表示Bessie认识一个长度（以音节为单位）为si、属于韵部ci的单词。
最后M行描述了Bessie想要的押韵模式，每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。
输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。