Se le proporciona una cadena de longitud ~n~ y un diccionario con ~k~ palabras. ¿De cuántas maneras puede crear la cadena usando las palabras?

Entrada

La primera línea de entrada contiene una cadena con ~n~ caracteres entre la ~a~ y la ~z~. La segunda línea contiene un entero ~k~: el número de palabras del diccionario. Finalmente, hay ~k~ líneas que describen las palabras. Cada palabra es única y consta de caracteres de la ~a~ a la ~z~.

Salida

Imprima el número de maneras módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 5000~
• ~1 \leq k \leq 10^5~
• La longitud total de las palabras es como máximo de ~10^6~.

Ejemplo de Entrada

ababc
4
ab
abab
c
cb

Ejemplo de Salida

2

Explicación: Las maneras posibles son ~ab+ab+c~ y ~abab+c~.