J - Contraseña

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Fito se va a crear una nueva cuenta de correo y solo le falta escribir la nueva contraseña. El sitio web que está usando le dice si la contraseña que ha escrito es segura o no. Después de algunos intentos de contraseñas evaluadas como poco seguras Fito decide que el sitio es tal vez demasiado injusto. Por ejemplo una contraseña debe tener al menos una letra mayúscula, una minúscula y un dígito o será considerada muy mala. Fito puede aceptar esta regla pero se enfada porque cuando intenta poner “Fito2018” es rechazada por contener su nombre y el año actual. Después de pasar tanto tiempo buscando una contraseña, Fito se rinde y decide seguir un link en la página que supuestamente explica como escoger una buena contraseña. La página a la que llega Fito tiene un conjunto de reglas que deben cumplir las contraseñas para ser consideradas seguras por el sistema. Al ver tantas reglas Fito decide contar cuantas contraseñas realmente cumplen todas las reglas.


Las reglas de forma resumida son las siguientes:

  • Las contraseñas solo contienen letras y dígitos. Las letras pueden ser minúsculas o mayúsculas.
  • La longitud de la contraseña ha de estar entre dos valores $A$ y $B$.
  • La contraseña debe tener al menos una letra mayúscula, una minúscula y un dígito.
  • Se ofrece un grupo de palabras que no pueden aparecer como subcadena de la contraseña.


La última regla es un poco fuerte porque puede considerar que la contraseña contiene una palabra ignorando la diferencia entre mayúsculas y minúsculas. Por ejemplo la palabra “fito” aparece en las contraseñas “Fito”, “FiTo” y “f170”. El último caso se cumple porque es posible sustituir algunos dígitos con letras, específicamente “0” por “o”, “1” por “i”, “3” por “e”, “5” por “s” y “7” por “t”.

Input

La primera línea de la entrada contiene dos enteros $A$ y $B (3 \leq A \leq B \leq 20)$  que indican la menor y mayor longitud de la contraseña respectivamente. La segunda línea es un entero $N (0 \leq N \leq 50)$ que representa la cantidad de palabras que no pueden ser subcadena de la contraseña. Le siguen las $N$ palabras en filas distintas. La longitud de cada palabra es un entero entre $1$ y $20$. Las letras que forman las palabras son letras minúsculas del alfabeto latino.

Output

Se debe imprimir la cantidad de contraseñas que cumplen todas las reglas. Como este número es muy grande se debe dar el resto de su división por $1000003$.

Sample test(s)

Input
3 5 3 hola mundo fito
Output
922715