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:
K
litere mici ale alfabetului englezN
date inițial sau din celelalte M − 1
nou formate astfel încât cuv
să fie prefix al cuvântului i
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
.
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.
Se va afișa pe o singură linie numărul de moduri de a forma cele M
cuvinte modulo 1.000.000.007
.
1 ≤ N ≤ 300.000
1 ≤ M ≤ 300.000
1 ≤ i ≤ M
S
suma lungimilor celor N
cuvinte inițiale. Atunci 1 ≤ S ≤ 300.000
1 ≤ K ≤ 26
K
litere mici ale alfabetului englez.K = 2
S ≤ 20
1 ≤ N, S ≤ 1000
N
, pentru orice 1 ≤ i ≤ N
M = 1
N = 1
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
Î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
.
ID: 65
Upload: liviu
Input: Console Input
Memory limit: 128MB/128MB
Time limit: 0.3s
Author: Alexandra Udristoiu
Source: ONI 2021 XI-XII: Problema 3