Green şi Riemann sunt doi prieteni buni cărora le place să joace un joc numit “enigma”. În acest joc, unul dintre ei scrie un cuvânt format din caractere, iar celălalt vine cu cuvinte de maxim caractere. Scopul celui de-al doilea jucător este să îşi dea seama în câte moduri poate primul cuvânt să fie format din concatenarea prefixelor unor cuvinte dintre cele .
Dacă s-a găsit un mod de a forma primul cuvânt, atunci fiecare poziţie a acestuia va avea asociată o pereche , semnificând faptul că poziţia i este acoperită de al -lea caracter din cuvântul . Astfel, două moduri de a forma primul cuvânt sunt considerate diferite dacă există două poziţii şi , cu perechile asociate şi astfel încât sau .
Cerință
Realizaţi un program care să rezolve jocul “enigma”!
Date de intrare
Fişierul de intrare enigma.in va conţine pe prima linie două numere şi cu semnificaţia din enunţ. A doua linie va conţine primul cuvânt format din caractere. Urmează linii, fiecare conţinând un cuvânt de maxim caractere.
Date de ieșire
Fişierul de ieşire enigma.out va conţine pe prima linie numărul de moduri în care primul cuvant poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele , modulo .
Restricții și precizări
- un caracter este definit ca fiind o literă mică din alfabetul englez
- un cuvânt poate apărea de mai multe ori
- prefixele cuvintelor pot fi doar concatenate, nu şi suprapuse
Exemplul 1
enigma.in
7 3
xxxabdc
xxx
abdc
c
enigma.out
8
Explicație
Considerând numerotarea cuvintelor cea din fişierul de intare, perechile asociate poziţiilor primului cuvânt sunt:
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;