Propozitie2

propozitie2

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

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.

Poveste şi cerinţă...

h2. Date de intrare

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.

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

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