28555번 - Связь с Эйвой 다국어

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

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

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

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