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 N caractere, iar celalalt vine cu M cuvinte de maxim S 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 M.
Dacă s-a găsit un mod de a forma primul cuvânt, atunci fiecare poziţie i a acestuia va avea asociată o pereche (x, y), semnificând faptul că poziţia i este acoperită de al y-lea caracter din cuvântul x. Astfel, două moduri de a forma primul cuvânt sunt considerate diferite dacă există două poziţii i şi j, cu perechile asociate (x1, y1) şi (x2, y2) astfel încât x1 != x2 sau y1 != y2.

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 N şi M cu semnificaţia din enunţ. A doua linie va conţine primul cuvânt format din N caractere. Urmează M linii, fiecare conţinând un cuvânt de maxim S 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 cuvânt poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele M, modulo 31 333.

Restricţii

• 1 ≤ N ≤ 300 000
• 1 ≤ M ≤ 4 500
• 1 ≤ S ≤ 100
• 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

Exemple

enigma.in	enigma.out	Explicaţii
7 3 xxxabdc xxx abdc c	8	Considerând numerotarea cuvintelor cea din fişierul de intare, perechile asociate poziţiilor primului cuvânt sunt: 1. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4); 2. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4); 3. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (2, 4); 4. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (2, 4); 5. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1); 6. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1); 7. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (3, 1); 8. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1)

autor: Andrei Parvu

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com