Без ведома фермера Джона Бесси - настоящая покровительница искусств! Совсем недавно она начала изучать многих великих поэтов, и теперь хочет попробовать написать собственные стихи. Бесси знает 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.