Поезія Корови
Без відома фермера Джона, Бессі стала справжньою покровителькою мистецтв! Нещодавно вона почала вивчати багатьох великих поетів і тепер хоче спробувати написати власні вірші. Бессі знає 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.