Problem 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:

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

General info

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

Submissions

Special Submissions