Беси хочет написать собственную поэму.
Беси знает \(N\) (\(1 \leq N \leq 5000\)) слов и хочет организовать их в поэму.
Она определила длину в слогах каждого слова, кроме того она распределила их в
"классы рифм". Каждое слово рифмуется только с другими словами из этого же класса
рифм.
Каждая из поэм Беси включает \(M\) строк (\(1 \leq M \leq 10^5\)) и каждая строка
должна состоять из \(K\) (\(1 \leq K \leq 5000\)) слогов. Более того, поэм Беси
должна соответствовать специфической схеме рифм.
Беси хочет узнать, сколько различных поэм она может написать, которые
удовлетворяют указанным ограничениям.
ФОРМАТ ВВОДА (файл poetry.in):
Первая строка ввода содержит
\(N\),
\(M\),
\(K\).
Каждая из следующих \(N\) строк содержит два числа \(s_i\) (\(1 \leq s_i \leq K\))
и \(c_i\) (\(1 \leq c_i \leq N\)). Они обозначают, что Беси знает слово с длиной
(в слогах) \(s_i\) и класса рифмы \(c_i\).
Последние \(M\) строк описывают желаемую схему рифмы Беси и каждая содержит
одну большую букву \(e_i\). Все строки соответствующие \(e_i\) должны заканчиваться
словами одного и того же кдасса рифм. Строки с различными значениями \(e_i\)
не обязательно заканчиваются словами с различными классами рифм.
ФОРМАТ ВЫВОДА (файл poetry.out):
Выведите количество поэм, которые может Беси написать, удовлетворяющих
все заданным ограничениям. Поскольку это число может быть очень велико,
выводите ответ по модулю 1,000,000,007.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 10
3 1
4 1
3 2
A
B
A
|
960
|