| Codeforces Round 299 (Div. 2) |
|---|
| Закончено |
Тавас — странное создание. Обычно, когда люди спят, от них доносится тихое "zzz", но от спящего Таваса доносится строка s длины n.
Сегодня Тавас уснул в гостях у Малекаса. Пока он спал, Малекас немного поработал со строкой s. У Малекаса есть своя любимая строка p. Он определил все позиции x1 < x2 < ... < xk, где p входит в s. Более формально, для каждого xi (1 ≤ i ≤ k) выполняется условие sxisxi + 1... sxi + |p| - 1 = p.
Затем Малекас записал одну из подпоследовательностей x1, x2, ... xk (возможно, пустую) на бумажке. По определению, b — это подпоследовательность последовательности a тогда и только тогда, когда мы можем получить b из a, удалив некоторые элементы (возможно, удалив все или не удалив ничего вовсе).
Когда Тавас проснулся, Малекас всё ему рассказал. Он не смог вспомнить строку s, но он знает, что и p, и s содержат только строчные буквы английского алфавита, а также у него есть подпоследовательность, записанная на бумажке.
Тавасу стало интересно: сколько различных строк s подходит под имеющуюся информацию? Он спросил СаДДаса, но СаДДас недостаточно умен, чтобы решить задачу. Итак, Тавас попросил вас посчитать это количество для него.
Ответ может быть очень большим, так что Тавас хочет, чтобы вы вывели его остаток от деления на 109 + 7.
В первой строке следуют два целых числа, n и m — длина s и длина записанной Малекасом подпоследовательности соответственно (1 ≤ n ≤ 106 and 0 ≤ m ≤ n - |p| + 1).
Во второй строке следует строка p (1 ≤ |p| ≤ n).
В следующей строке следует m целых чисел через пробел y1, y2, ..., ym, подпоследовательность Малекаса (1 ≤ y1 < y2 < ... < ym ≤ n - |p| + 1).
В единственной строке выведите ответ по модулю 1 000 000 007.
6 2
ioi
1 3
26
5 2
ioi
1 2
0
В первом тесте из условия подходят все строки вида "ioioi?", где вместо вопросительного знака может стоять любая буква английского алфавита.
Здесь |x| обозначает длину строки x.
Обратите внимание, что такой строки может не существовать, в таком случае ответ — 0.
