G. Вкусный десерт
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня у повара Тонио важный день — в его родной город Морио приехал ревизор. Он доехал и до ресторана Тонио и заказал у него десерт. Тонио к такому повороту событий не был готов.

Как известно, десерт — это строка из строчных латинских символов. Тонио вспомнил общее правило десертов — строку $$$s$$$ длины $$$n$$$. Любой десерт $$$t$$$ является вкусным, если количество вхождений строки $$$t$$$ в строку $$$s$$$ как подстроки делится нацело на длину $$$t$$$.

Теперь Тонио хочет знать количество вкусных подстрок заготовки $$$s$$$. Если подстрока встречается в строке $$$s$$$ несколько раз, то в ответе нужно учесть все вхождения.

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

В первой строке дано целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — длина правила $$$s$$$.

Во второй строке находится строка $$$s$$$ длины $$$n$$$ — правило десертов. Правило состоит только из строчных букв латинского алфавита.

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

В единственной строке выведите количество подстрок строки $$$s$$$, являющихся вкусными десертами.

Примеры
Входные данные
7
abacaba
Выходные данные
11
Входные данные
8
abaababa
Выходные данные
11
Входные данные
10
deadinside
Выходные данные
12
Входные данные
5
aaaaa
Выходные данные
12
Примечание

В первом примере есть много вкусных подстрок — $$$7$$$ из них это подстроки длины $$$1$$$ (так как любое число делится на $$$1$$$ нацело). Рассмотрим другие вкусные подстроки:

  • «ab» встречается в $$$s$$$ $$$2$$$ раза, что делится на длину подстроки.
  • «ba» также встречается $$$2$$$ раза.

Следовательно ответ $$$7 + 2 + 2 = 11$$$.

Обратите внимание, что в ответе учтены оба вхождения как «ab», так и «ba».