Se dau N
cuvinte formate doar din primele K
litere mici ale alfabetului englez și un șir 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
- Să fie format doar din primele
K
litere mici ale alfabetului englez - Să nu existe niciun cuvânt
cuv
din celeN
date inițial sau din celelalteM − 1
nou formate astfel încâtcuv
să fie prefix al cuvântuluii
- Să nu existe niciun cuvânt
cuv
din celeN
date inițial sau din celelalteM − 1
nou formate astfel încât cuvântuli
să fie prefix al luicuv
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 , 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
- , pentru orice
1 ≤ i ≤ M
- Fie
S
suma lungimilor celorN
cuvinte inițiale. Atunci1 ≤ 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
S ≤ 20
Subtask 2 (19 puncte)
Subtask 3 (11 puncte)
1 ≤ N, S ≤ 1000
Subtask 4 (12 puncte)
- lungimea oricărui cuvânt inițial dintre cele
N
, pentru orice1 ≤ 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
.