Сегодня у повара Тонио важный день — в его родной город Морио приехал ревизор. Он доехал и до ресторана Тонио и заказал у него десерт. Тонио к такому повороту событий не был готов.
Как известно, десерт — это строка из строчных латинских символов. Тонио вспомнил общее правило десертов — строку \(s\) длины \(n\). Любой десерт \(t\) является вкусным, если количество вхождений строки \(t\) в строку \(s\) как подстроки делится нацело на длину \(t\).
Теперь Тонио хочет знать количество вкусных подстрок заготовки \(s\). Если подстрока встречается в строке \(s\) несколько раз, то в ответе нужно учесть все вхождения.
В первой строке дано целое число \(n\) (\(1 \leq n \leq 10^6\)) — длина правила \(s\).
Во второй строке находится строка \(s\) длины \(n\) — правило десертов. Правило состоит только из строчных букв латинского алфавита.
В единственной строке выведите количество подстрок строки \(s\), являющихся вкусными десертами.
В первом примере есть много вкусных подстрок — \(7\) из них это подстроки длины \(1\) (так как любое число делится на \(1\) нацело). Рассмотрим другие вкусные подстроки:
Следовательно ответ \(7 + 2 + 2 = 11\).
Обратите внимание, что в ответе учтены оба вхождения как «ab», так и «ba».
7 abacaba
11
8 abaababa
10 deadinside
12
5 aaaaa
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач