Поезія Корови#10335
Без відома фермера Джона, Бессі стала справжньою покровителькою мистецтв! Нещодавно вона почала вивчати багатьох великих поетів і тепер хоче спробувати написати власні вірші. Бессі знає слів і хоче скласти з них вірші. Вона визначила кількість складів у кожному зі своїх слів і розподілила їх по "класах рим". Кожне слово римується тільки з іншими словами того ж класу рими.
Кожен вірш Бессі складається з рядків, кожен з яких повинен містити складів. Крім того, вірші Бессі повинні дотримуватися певної схеми рим.
Бессі хоче дізнатися, скільки різних віршів вона може скласти, дотримуючись заданих обмежень.
Перша строка містить числа (1 \le n \le 5000), (1 \le m \le 10^5) і (1 \le k \le 5000). Кожен з наступних рядків містить два числа s_i (1 \le s_i \le k) і c_i (1 \le c_i \le n). Це означає, що Бессі знає слово довжиною (в складах) s_i у класі рими c_i.
Останні рядків описують бажану Бессі схему рим, кожен з яких містить одну велику літеру e_i. Усі рядки, що відповідають однаковим значенням e_i, повинні закінчуватися словами з одного й того ж класу рими. Рядки з різними значеннями e_i не обов'язково закінчуються словами з різних класів рими.
Виведіть кількість віршів, які Бессі може скласти, дотримуючись цих обмежень. Оскільки це число може бути дуже великим, обчисліть його за модулем 10^9 + 7.
У заданому прикладі Бессі знає три слова. Перші два слова римуються і складаються з трьох і чотирьох складів, а останнє слово складається з трьох складів і не римується з іншими. Вона хоче написати вірш з трьох рядків, у якому кожен рядок містить десять складів, а перший і останній рядки римуються. Таких віршів . Приклад одного з таких віршів (, і представляють перше, друге і третє слово): 121 123 321.
Приклад 1