Задачи очного тура личного первенства

Возьмем какой-нибудь осмысленный текст, предварительно удалив из него все знаки препинания, например, "alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do" и подсчитаем частоту появления каждой буквы или пробела в этой фразе. Мы можем сгенерировать текст, выбирая очередной символ с вероятностью, с которой этот символ встречаются в исходной фразе, но результат будет слишком отличаться от естественного текста: "iehehgv bwbertieitneisediiigiiidgrhs sn obi b i nlo nntthtesi oiin oihaetengdet ditfaoo hrhbebc". Cлова невозможно произнести, они часто слишком длинные или совсем короткие. Намного лучший результат дает использование алгоритма цепей Маркова, в котором анализируются вероятности появления пар символов и очередной символ генерируется с учетом предыдущего символа текста: "sinnk ve her walindof thinoto d tink aninged tind histo nof othe of bang tisingite oto to singing to". Вероятность выбора очередного символа текста `A_i` прямо пропорцинальна вероятности появления пары `A_{i-1}A_i` в исходной фразе. Для первого символа текста предыдущим (`A_0`) является пробел, также пробелы добавляются в начале и в конце исходной фразы перед вычислением вероятности появления пар. Длина слов в получившемся тексте более естественна, их можно произнести, можно отметить появление английских слов bang и singing, отсутствовавших в исходной фразе. Неспециалист даже может принять этот текст за текст на незнакомом ему языке.

Напишите программу, которая подсчитывает количество различных слов длины `N` в бесконечном тексте, сгенерированном указанным алгоритмом. Словом считается часть текста между пробелами, состоящая только из букв.

Первая строка ввода содержит два целых числа – длина слов `N` (`1\ ≤\ N\ ≤\ 10^9`) и число `P` (`10\ ≤\ P\ ≤\ 10^9`). Вторая строка ввода содержит исходную фразу длиной не более 1000 символов, состоящую только из строчных латинских букв и символов пробела.

Вывести одно целое число – остаток от деления на число `P` количества различных слов длины `N` в бесконечном сгенерированном тексте.

2 100
alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do

20

Пояснение в ходе соревнований:

Пусть пара символов `A_{i-1}B_j` встречается в исходной фразе `K_j` раз, где `B_j` кандидат на `i`-й символ генерируемого текста, тогда вероятность выбора символа `B_j` в качестве `A_i` равна `K_j/{sum_m\ K_m}`. Т.е. если пара символов `"xy"` не встречается в исходной фразе, то она никогда не появится в генерируемом тексте.