Связь с Эйвой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ученые, изучающие Пандору, выяснили, что вся планета — один большой живой организм, соединенный с коллективным сознанием — Эйвой. Все живые существа на Пандоре могут устанавливать с ней связь и общаться с ней.

Для создания нового прототипа Аватаров ученые решили сфокусироваться на том, чтобы Аватары были ближе к Эйве и получили возможность контролировать явления на планете с ее помощью. Для этого они редактируют генетический код текущего поколения Аватаров.

Всего в текущем поколении $$$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$$$, состоящая из маленьких букв латинского алфавита, из которой циклическими сдвигами можно получить генетические коды всех особей первого поколения.

Выходные данные

Выведите единственное число — количество пар особей первого поколения, при рекомбинации которых получается не представленный в первом поколении генетический код.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
115$$$n \le 10$$$полная
217
$$$s_i \in \{\text{'\t{a}'}, \text{'\t{b}'}\}$$$ для всех $$$i$$$; количество 'b' в строке $$$\leqslant 2$$$
первая ошибка
317$$$n \le 100$$$1первая ошибка
423$$$n \le 1000$$$3первая ошибка
528нет1 — 4первая ошибка

Примеры

Входные данные
4
abcd
Выходные данные
12
Входные данные
4
abab
Выходные данные
8
Входные данные
12
aabbccaabbcc
Выходные данные
48