Сколько коллизий даёт один модуль

1000 мс · 256 МБ · всё или ничего

Даны строка $s$ , длина $k$ и параметры полиномиального хеша - основание $p$ и модуль $q$ . Хеш куска длины $k$ , начинающегося в позиции $i$ , считается как

h_i = \left(s_i p^{k-1} + s_{i+1} p^{k-2} + \ldots + s_{i+k-1}\right) \bmod q,

где буква кодируется своим ASCII-кодом.

Посчитайте количество пар позиций $i < j$ , у которых хеши совпали, а сами куски различны. Это и есть число коллизий.

Формат ввода

В первой строке - строка $s$ из строчных латинских букв ( $1 \le |s| \le 3000$ ).

Во второй строке - числа $k$ , $p$ и $q$ ( $1 \le k \le |s|$ , $2 \le p < q \le 10^9$ ).

Формат вывода

Выведите количество пар позиций, у которых хеши совпали, а куски различны.

Примеры

ввод

aaaa
2 31 1000000007

вывод

ввод

abab
2 31 1000000007

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.