CSES - Sanakirja
  • Time limit: 1.00 s
  • Memory limit: 128 MB
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.