Sin que el granjero John lo sepa, Bessie es toda una entusiasta de las artes. Recientemente, ha comenzado a estudiar a muchos de los grandes poetas y ahora quiere intentar escribir su propia poesía.

Bessie sabe ~N (1 \leq N \leq 5000)~ palabras y quiere ordenarlas en poemas. Bessie ha determinado la longitud, en sílabas de cada una de sus palabras, y también las ha asignado en "clases de rima". Cada palabra rima sólo con otras palabras de la misma clase de rima.

Cada uno de los poemas de Bessie incluye ~M~ versos ~(1 \leq M \leq 10^5)~, y cada verso debe constar de ~K (1 \leq K \leq 5000)~ sílabas. Además, la poesía de Bessie debe ajustarse a un esquema de rima específico.

Bessie desea saber cuántos poemas diferentes puede escribir que satisfagan las restricciones dadas.

Entrada

La primera línea de entrada contiene ~N, M~ y ~K~. Las siguientes ~N~ líneas de entrada contienen cada una dos números ~s_i~ ~(1 \leq s_i \leq K)~ y ~c_i~ ~(1 \leq c_i \leq N)~. Esto indica que Bessie conoce una palabra con longitud (en sílabas) ~s_i~ en la clase de rima ~c_i~. Las últimas ~M~ líneas de entrada describen el esquema de rima deseado por Bessie y cada una contiene una letra mayúscula ~e_i~. Todas las líneas correspondientes a valores iguales de ~e_i~ deben terminar con palabras de la misma clase de rima. Las líneas con valores diferentes de ~e_i~ no necesariamente terminan con palabras de diferentes clases de rima.

Salida

Imprima el número de poemas que Bessie puede escribir y que satisfacen estas restricciones. Como este número puede ser muy grande, por favor, calcúlelo módulo ~10^9 + 7~.

Ejemplo de Entrada

3 3 10
3 1
4 1
3 2
A   
B    
A

Ejemplo de Salida

960

En este ejemplo, Bessie conoce tres palabras. Las dos primeras palabras riman y tienen longitudes de tres y cuatro sílabas, y la última palabra tiene tres sílabas y no rima con las otras. Quiere escribir un poema de tres versos que contenga diez sílabas cada uno y que el primer y el último verso rimen. Hay ~960~ poemas de este tipo. Un ejemplo de poema válido es el siguiente (donde ~1, 2~ y ~3~ representan la primera, la segunda y la tercera palabra): ~121~ ~123~ ~321~