== include(page="template/taskheader" task_id="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:

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

h2. Date de intrare

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

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.

h2. Date de ieşire

În fişierul de ieşire $cuvinte6.out$ ...

Î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$.

h2. 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.
 
h2. Subtaskuri
 
* *Subtask 1 (8 puncte)*
** $K = 2$
** <tex>\sum_{i = 1}^{M} x_i \leq 18 </tex>
** S &le; 20
 
* *Subtask 2 (19 puncte)*
** $1 &le; N,M,S,x{~i~} &le; 1000$
 
* *Subtask 3 (11 puncte)*
** $1 &le; N,S &le; 1000$
** $1 &le; M,x{~i~} &le; 300000$
 
* *Subtask 4 (12 puncte)*
** $x{~i~}$ > lungimea oricărui cuvânt iniţial dintre cele $N$, pentru orice $1 &le; i &le; N$
 
* *Subtask 5 (11 puncte)*
** $M = 1$
 
* *Subtask 6 (7 puncte)*
** $N = 1$
 
* *Subtask 7 (32 de puncte)*
** Fără restricţii suplimentare

h2. Exemplu
table(example). |_. cuvinte6.in |_. cuvinte6.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 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 |

h3. 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$.

== include(page="template/taskfooter" task_id="cuvinte6") ==