Los azucareros del centro en sus registros secretos usan palabras de tamaño a lo sumo de ~3*10^5~ caracteres. Escriba el programa que halle la cantidad de formas de dividir una palabra en varias "piezas" tal que cada "pieza" pertenezca a un conjunto de palabras. Como esto puede ser muy grande imprímalo módulo ~1337377~.

Entrada

La primera línea contiene la palabra dada. La segunda línea contiene un entero ~n~ ~(1 \leq n \leq 4000)~, el tamaño del conjunto ~S~. Cada una de las siguientes ~n~ líneas contiene una palabra ~w~ tal que ~w \in S~ , esto es, una palabra del conjunto ~S~. Cada una de estas palabras tendrá a lo sumo 100 caracteres. No habrá dos palabras idénticas y todos los caracteres serán letras minúsculas del alfabeto Inglés. Note que puede usar una palabra ~w~ cualquier cantidad de veces.

Salida

En una única línea imprima la respuesta del problema módulo ~1337377~.

Ejemplos #1 de Entrada

abcd
4
a
b
cd
ab

Ejemplos #1 de Salida

2

Ejemplo #2 de Entrada

afrikapaprika
4
afr
ika
pap
r

Ejemplo #2 de Salida

1

Ejemplo #3 de Entrada

ababababababababababababababababababababab
3
a
b
ab

Ejemplo #3 de Salida

759775

Explicación del primer ejemplo: Las formas son: ~a - b - cb~ y ~ab - cd~.