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

12

stdin

6 5 3
aab
aabcc
aabb
bbb
bb
aaaab
2
3
6
5
5

stdout

925829353

Explicații

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