CSES - Sanakirja
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

Syöte

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

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

Lopuksi syötteessä on kk 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 109+710^9+7.

Rajat

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

Esimerkki

Syöte:

ababc
4
ab
abab
c
cb

Tuloste:

2

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