Problem 65: cuvinte

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

Cerință

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

Prima linie conține 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

Se va afișa pe o singură linie numărul de moduri de a forma cele M cuvinte modulo 1 000 000 007.

Restricții și precizări

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

Subtask 1 (8 puncte)

K = 2
$\sum_{i=1}^M x_i ≤ 18$
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 ≤ 300 \ 000$

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

Exemple

stdin

4 2 2
ab
abaa
bbb
baaa
3
3

stdout