propozitie2

Propozitie2

== include(page="template/taskheader" task_id="propozitie2") ==

Poveste şi cerinţă...

Dubota a primit ca tema de la profesoara de informatica sa imparta un text in propozitii si apoi in cuvinte. Insa cum el nu era atent si-a notat altceva ca tema. El primeste un sir S si un dictionar format din C cuvinte. Cuvintele se identifica insa numai prin caracterele din care sunt formate, asadar orice permutare a caracterelor unui cuvant reprezinta acelasi cuvant. De exemplu, daca avem un cuvant identificat prin caractere "adt" atunci si succesiunile de caractere urmatoare: "dat" sau "tda" sau "tad" reprezinta acelasi cuvant.
Acum Dubota trebuie sa imparte sirul initial in cuvinte care sa formeze o propozitie. O propozitie este o succesiune de cuvinte astfel incat fiecare caracter al sirului initial apartine unui cuvant si numai unul, iar orice cuvant face parte din dictionar. Intr-o propozitie un cuvant din dictionar poate sa apara de mai multe ori.
 
h2. Cerinta
 
Sa se determine cate posibilitati are Dubota pentru a imparti sirul S in propozitii. Deoarece acest rezultat poate fi foarte mare, este de ajuns sa determinati rezultatul modulo 666019.

h2. Date de intrare

Fişierul de intrare $propozitie2.in$ ...

Pe prima linie se afla un sir de caractere, S, iar pe a doua linie se afla un numar, C. Pe urmatoarele C linii se afla cate un sir de caractere reprezentant un cuvant al dicitionarului.

h2. Date de ieşire

Se va afisa un singur numar, reprezentant rezultatul cerut.
 

În fişierul de ieşire $propozitie2.out$ ...
h2. Restricţii