Fişierul intrare/ieşire:	cuvinte6.in, cuvinte6.out	Sursă	ONSEPI, clasele 11-12
Autor	Alexandra Udristoiu	Adăugată de	Nicola Alexandra Mihaela •Nicolaalexandra
Timp execuţie pe test	0.25 sec	Limită de memorie	512000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cuvinte6

Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez şi un şir x_i de M numere naturale. Trebuie să se formeze M cuvinte astfel încât oricare cuvânt i ( 1 ≤ i ≤ M ) să respecte următoarele proprietăţi:

• Să aibă lungimea x_i
• Să fie format doar din primele K litere mici ale alfabetului englez
• Să nu existe niciun cuvânt cuv din cele N date iniţial sau din celelalte M − 1 nou formate astfel încât cuv să fie prefix al cuvântului i
• Să nu existe niciun cuvânt cuv din cele N date iniţial sau din celelalte M − 1 nou formate astfel încât cuvântul i să fie prefix al lui cuv

Să se calculeze numărul de moduri de a forma M cuvinte care respectă proprietăţile de mai sus. Două moduri se consideră diferite dacă există cel puţin o poziţie i pentru care al i-lea cuvânt diferă. Deoarece acest număr poate fi foarte mare, se va afişa doar restul său la împărţirea cu 1.000.000.007.

Date de intrare

Fişierul de intrare cuvinte6.in conţine pe prima linie 3 numere naturale separate prin câte un spaţiu N, M şi K, având semnificaţia din enunţ. Pe următoarele N linii se află câte un şir de caractere reprezentând cuvintele iniţiale. Ultimele M linii conţin câte un număr natural x_i, reprezentând lungimile cuvintelor care trebuie construite.

Date de ieşire

În fişierul de ieşire cuvinte6.out se va afişa pe o singură linie cu numărul de moduri de a forma cele M cuvinte modulo 1.000.000.007.

Restricţii

• 1 ≤ N ≤ 300000
• 1 ≤ M ≤ 300000
• 1 ≤ x_i ≤ 300000, pentru orice 1 ≤ i ≤ M
• Fie S suma lungimilor celor N cuvinte iniţiale. Atunci 1 ≤ S ≤ 300000
• 1 ≤ K ≤ 26
• Se garantează că toate cuvintele iniţiale vor fi formate doar din primele K litere mici ale alfabetului englez.

Subtaskuri

• Subtask 1 (8 puncte)
  • K = 2
  • 
  • S ≤ 20

• Subtask 2 (19 puncte)
  • 1 ≤ N,M,S,x_i ≤ 1000

• Subtask 3 (11 puncte)
  • 1 ≤ N,S ≤ 1000
  • 1 ≤ M,x_i ≤ 300000

• Subtask 4 (12 puncte)
  • x_i > lungimea oricărui cuvânt iniţial dintre cele N, pentru orice 1 ≤ i ≤ N

• Subtask 5 (11 puncte)
  • M = 1

• Subtask 6 (7 puncte)
  • N = 1

• Subtask 7 (32 de puncte)
  • Fără restricţii suplimentare

Exemplu

cuvinte6.in	cuvinte6.out
4 2 2 ab abaa bbb baaa 3 3	12
6 5 3 aab aabcc aabb bbb bb aaaab 2 3 6 5 5	925829353

Explicaţie

În primul exemplu, există 4 posibilităţi de a forma un cuvânt de lungime 3: aaa, aab, bab, bba, şi 12 posibilităţi de a forma două cuvinte de lungime 3.

Cum se trimit solutii?