En su usualmente torpe manera, las vacas están jugando una versión de Yahtzee el juego de tirar dados. Ellas tiran ~N~ ~(1 \leq N \leq 20)~ dados, cada uno de ~S~ ~(1 \leq S \leq 8)~ lados. Ellas tienen curiosidad de saber el número de maneras en que una tirada de dados puede satisfacer un criterio particular (como contiene tres 2's o "contiene un 2 y dos 3's).

Ayúdelas a aprender acerca de probabilidades. Escriba un programa que lea no solamente ~N~ y ~S~, pero también algunas expresiones que describan su criterio. Cuente el número de maneras en las que la expresión puede ser satisfecha sobre todo el conjunto de todos los posibles lanzamientos de dados (todo el conjunto de tiros para dados de tres dados de dos caras es: {~1,1,1~; ~1,1,2~; ~1,2,1~; ~1,2,2~; ~2,1,1~; ~2,1,2~; ~2,2,1~; ~2,2,2~}.

Las expresiones abarcan combinaciones de una forma básica que expresa el pensamiento "quiero al menos ~W~ copias del resultado ~R~". Se ven como esto: ~WxR~ donde ~(0 \leq W \leq N~ y ~1 \leq R \leq S)~. Cada ejecución de prueba proporcionará ~E~ expresiones ~(1 \leq E \leq 20)~, cada una de las cuales contiene un número ~1..10~ de las formas básicas separadas por un '+', el cual quiere decir 'y' (ver a continuación). El conjunto de líneas expresa el pensamiento que es 'o inclusive' de cada una de las líneas individualmente. Por lo tanto el par de expresiones mostradas quieren decir "al menos tres tiros de cinco O ambos al menos un tiro de 3 y también al menos dos tiros de 4":

3x5
1x3+2x4

Aquí hay algunas de las combinaciones de cuatro dados de cinco lados que satisfacen la expresión antes dada: ~5,5,5,1~; ~4,5,5,5~; ~3,4,4,2~; ~3,4,4,3~; ~3,4,4,5~; ~4,4,5,3~.

Nota de Programación: Esté seguro de que usted pueda leer dos enteros de una línea y una cadena de la siguiente línea. ¡en el esquema de Entrada/Salida de algunos lenguajes, esto es más difícil de lo que parece!

También note que el número total de combinaciones de dados jamás excederá 1,512,768 en los conjuntos de entrada a usar.

Entrada

• Línea 1: Tres enteros separados por espacios: ~N, S~ y ~E~.
• Líneas 2..E+1: La línea i+1 describe la expresión ~i~ como se ha especificado anteriormente.

Ejemplo de Entrada

4 5 2
3x5
1x3+2x4

Detalles de la Entrada: Esta es la codificación de la expresión usada como ejemplo en el texto de la tarea.

Salida

Un solo entero que es el número de maneras que la(s) expresión(es) pueden ser satisfechas arrojando los dados en todas las combinaciones.

Ejemplo de Salida

63

Detalles de la Salida: ~63~ tiros satisfacen la expresión.