eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Вершины неявного суффиксного дерева

Вершины неявного суффиксного дерева

Лимит времени 0.5 секунд
Лимит использования памяти 256 MiB

Суффиксное дерево — называется неявным, если оно содержит как неявный бор все суффиксы строки и при этом содержит минимальное количество вершин. Например, неявное суффиксное дерево строки "ababa" выглядит так, как показано на рисунке ниже (в нем имеются 3 вершины):

Вам задана строка s, как конкатенация k копий строки t. То есть, . Посчитайте количество вершин в неявном суффиксном дереве строки s.

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

В первой строке записано целое число k (1k10^9). Во второй строке записана строка t (1|t|10). Строка t состоит только из маленьких латинских букв.

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

Выведите единственное целое число — количество вершин в неявном суффиксном дереве строки s.

Пример

Входные данные #1
1000
a
Выходные данные #1
2
Автор Геральд Агапов
Источник Летняя школа Севастополь 2013, Волна 1, День 6