Annettuna on merkkijono, jossa on n merkkiä, sekä sanakirja, jossa on k sanaa. Montako tapaa on muodostaa merkkijono laittamalla peräkkäin sanakirjan sanoja?

Syöte

Syötteen ensimmäisellä rivillä on merkkijono, jossa on n merkkiä.

Seuraavalla rivillä on kokonaisluku k: sanojen määrä.

Lopuksi syötteessä on k riviä, joista jokainen sisältää yhden sanan. Sama sana ei esiinny monta kertaa.

Kaikissa merkkijonoissa aakkostossa on merkit a–z.

Tuloste

Tulosta tapojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 5000
• 1 \le k \le 10^5
• sanojen yhteispituus on enintään 10^6

Esimerkki

Syöte:

ababc
4
ab
abab
c
cb

Tuloste:

2

Selitys: Tavat ovat ab+ab+c ja abab+c.