cuvinte

Time limit: 0.3s Memory limit: 128MB Input: Output:

Se dau N cuvinte formate doar din primele K litere mici ale alfabetului englez și un șir xix_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 xix_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 xix_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
  • 1xi300 0001 ≤ 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
  • i=1Mxi18\sum_{i=1}^M x_i ≤ 18
  • S ≤ 20

Subtask 2 (19 puncte)

  • 1N,M,S,xi10001 ≤ N, M, S, x_i ≤ 1000

Subtask 3 (11 puncte)

  • 1 ≤ N, S ≤ 1000
  • 1M,xi300 0001 ≤ M, x_i ≤ 300 \ 000

Subtask 4 (12 puncte)

  • xi>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.

Log in or sign up to be able to send submissions!