- Time limit: 1.00 s
- Memory limit: 128 MB
Annettuna on merkkijono, jossa on merkkiä, sekä sanakirja, jossa on sanaa. Montako tapaa on muodostaa merkkijono laittamalla peräkkäin sanakirjan sanoja?
Syöte
Syötteen ensimmäisellä rivillä on merkkijono, jossa on merkkiä.
Seuraavalla rivillä on kokonaisluku : sanojen määrä.
Lopuksi syötteessä on 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 .
Rajat
- sanojen yhteispituus on enintään
Esimerkki
Syöte:
ababc 4 ab abab c cb
Tuloste:
2
Selitys: Tavat ovat ab+ab+c
ja abab+c
.