Cartel Bilingüe (2) P30660

Como sabréis, en Kazajistán se hablan dos lenguas: kazajo y ruso. Por eso típicamente los carteles están en ambos idiomas: primero en kazajo y a continuación en ruso. Además, a veces ponen todas las palabras juntas, una detrás de otra, sin ni siquiera separar entre los dos idiomas. Vuestra tarea es intentar descifrar uno de esos carteles.

Disponéis de un diccionario de kazajo y un diccionario de ruso, el primero con $k$ palabras y el segundo con $r$ palabras. (Aunque ambos idiomas se escriben en cirílico, nosotros usaremos una transliteración al alfabeto latino.) Como el kazajo y el ruso son lenguas totalmente diferentes, es posible que la traducción de uno a otro no tenga nada que ver, ni en número de palabras ni en longitud. Además, podría ser que el cartel estuviera en un solo idioma, ya sea kazajo o ruso. ¿De cuantas maneras posibles se podría descifrar el cartel?

Entrada

La entrada empieza con $k$, seguido de las $k$ palabras kazajas, seguido de $r$, seguido de las $r$ palabras rusas. Al final viene un cartel de longitud $c$. Ambos diccionarios tienen entre 1 y 20000 palabras. Tanto las palabras como el cartel contienen sólo letras minúsculas. La longitud de las palabras está entre 1 y 200, y $c$ está entre 1 y 20000. No hay palabras repetidas dentro del mismo diccionario.

Salida

Escribid el número de formas de descifrar el cartel, módulo $10^9 + 7$.

Puntuación

• Test1:

  Resolver entradas donde $k$ y $r$ son como mucho 1000, y $c$ es como mucho 10.

• Test2:

  Resolver entradas donde $c$ es como mucho 10.

• Test3:

  Resolver entradas de todo tipo.