Ученые, изучающие Пандору, выяснили, что вся планета — один большой живой организм, соединенный с коллективным сознанием — Эйвой. Все живые существа на Пандоре могут устанавливать с ней связь и общаться с ней.
Для создания нового прототипа Аватаров ученые решили сфокусироваться на том, чтобы Аватары были ближе к Эйве и получили возможность контролировать явления на планете с ее помощью. Для этого они редактируют генетический код текущего поколения Аватаров.
Всего в текущем поколении $$$n$$$ аватаров ($$$n$$$ четно), $$$i$$$-й из которых имеет фрагмент генетического кода, отвечающий за связь с Эйвой, равный циклическому сдвигу некоторой строки $$$s$$$ длины $$$n$$$ на $$$i$$$ позиций, то есть содержащий символы $$$s_i, s_{i+1}, \ldots, s_n, s_1, s_2, \ldots, s_{i-1}$$$.
Новых Аватаров планируют получать с помощью рекомбинации: берутся генетические коды двух Аватаров первого поколения и выписываются посимвольно по очереди: первый символ из первой особи, второй из второй, третий из первой, и так далее. Таким образом, при рекомбинации $$$i$$$-го и $$$j$$$-го Аватаров, получается строка $$$s_i, s_{(j+1) \bmod n}, s_{(i+2) \bmod n}, s_{(j+3) \bmod n}, \ldots, s_{(i+n-2) \bmod n}, s_{(j+n-1) \bmod n}$$$.
Ученых интересует, сколько существует пар особей первого поколения, при рекомбинации которых получится новый, не представленный в первом поколении, генетический код, отвечающий за возможность связи с Эйвой. Если существуют две пары особей $$$(i_1, j_1)$$$ и $$$(i_2, j_2)$$$, для которых получается один и тот же новый генетический код, в ответе следует учесть обе из них.
В первой строке входных данных дано одно четное число $$$n$$$ — длина генетического кода и количество особей в первом поколении ($$$2 \leqslant n \leqslant 10^6$$$).
Во второй строке дана исходная строка $$$s$$$, состоящая из маленьких букв латинского алфавита, из которой циклическими сдвигами можно получить генетические коды всех особей первого поколения.
Выведите единственное число — количество пар особей первого поколения, при рекомбинации которых получается не представленный в первом поколении генетический код.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 15 | $$$n \le 10$$$ | полная | |
2 | 17 | первая ошибка | ||
3 | 17 | $$$n \le 100$$$ | 1 | первая ошибка |
4 | 23 | $$$n \le 1000$$$ | 3 | первая ошибка |
5 | 28 | нет | 1 — 4 | первая ошибка |
4 abcd
12
4 abab
8
12 aabbccaabbcc
48