Поэзия Коровы
Без ведома фермера Джона Бесси - настоящая покровительница искусств! Совсем недавно она начала изучать многих великих поэтов, и теперь хочет попробовать написать собственные стихи. Бесси знает n слов и хочет сложить из них стихи. Бесси определила длину в слогах каждого своего слова, а также распределила их по "классам рифм". Каждое слово рифмуется только с другими словами того же класса рифмы.
Каждое стихотворение Бесси включает m строк, каждая из которых должна состоять из k слогов. Более того, стихи Бесси должны придерживаться определенной схемы рифм.
Бесси хочет узнать, сколько разных стихов она может написать, удовлетворяя заданным ограничениям.
Входные данные
Первая строка содержит числа n (1 ≤ n ≤ 5000), m (1 ≤ m ≤ 10^5) и k (1 ≤ k ≤ 5000). Каждая из следующих 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.
Пример
В заданном примере Бесси знает три слова. Первые два слова рифмуются и состоят из трех и четырех слогов, а последнее слово состоит из трех слогов и не рифмуется с другими. Она хочет написать стихотворение из трех строк, в котором каждая строка содержит десять слогов, а первая и последняя строки рифмуются. Таких стихотворений 960. Пример одного из таких стихов (1, 2 и 3 представляют первое, второе и третье слово): 121 123 321.