Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez și un șir xi 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 xi
• 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ța

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 trei 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 xi 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 ≤ xi ≤ 300.000, pentru orice 1 ≤ i ≤ M
• 1 ≤ S ≤ 300.000, unde S suma lungimilor celor N cuvinte inițiale
• 1 ≤ K ≤ 26
• Se garantează că toate cuvintele inițiale vor fi formate doar din primele K litere mici ale alfabetului englez.

Exemplul 1:

Intrare

4 2 2
ab
abaa
bbb
baaa
3
3

Ieșire

12

Explicație

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.

Exemplul 2:

Intrare

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

Ieșire

925829353