Como todos los bovinos, las vacas del granjero John hablan el peculiar lenguaje de las "vacas". Como tantos otros idiomas, cada palabra en este idioma comprende una secuencia de letras mayúsculas y minúsculas (A-Z y a-z). Una palabra es válida si y sólo si cada par de letras adyacentes ordenadas en la palabra es un par válido.

El granjero John, siempre preocupado de que sus vacas estén conspirando en su contra, recientemente trató de escuchar a escondidas su conversación. Escuchó una palabra antes de que las vacas notaran su presencia. El idioma de las vacas se habla tan rápido, y sus sonidos son tan extraños, que todo lo que el Granjero John pudo percibir fue el número total de letras mayúsculas, ~U (1 <= U <= 250)~ y el número total de letras minúsculas, ~L (1 <= L <= 250)~ en la palabra.

El granjero John conoce todas las ~P (1 <= P <= 200)~ pares ordenados válidos de letras adyacentes. Desea saber cuántas palabras válidas diferentes son coherentes con sus datos limitados. Sin embargo, como este número puede ser muy grande, sólo necesita el valor modulo 97654321.

Especificación de entrada

• Línea 1: Tres enteros separados por espacio: ~U, L y P~.
• Líneas 2..~P+1~: Dos letras (cada una de las cuales puede ser mayúscula o minúscula), que representan un par de letras adyacentes ordenadas válidas en Cow.

Especificación de salida

• Línea 1: Un solo entero, el número de palabras válidas que concuerdan con los datos del Granjero John, ~mod~. 97654321.

Ejemplo de entrada

2 2 7
AB
ab
BA
ba
Aa
Bb
bB

Ejemplo de salida

7

Sugerencia(s)

AabB
ABba
abBA
BAab
BbBb
bBAa
bBbB