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

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.