Задачи
Вершины неявного суффиксного дерева (Hard)
Вершины неявного суффиксного дерева (Hard)
Суффиксное дерево — называется неявным, если оно содержит как неявный бор все суффиксы строки и при этом содержит минимальное количество вершин.
Например, неявное суффиксное дерево строки "ababa" выглядит так, как показано на рисунке ниже (в нем имеются 3 вершины):
Вам задана строка s, как конкатенация k копий строки t. То есть, s = t + t + t + ... + t = . Посчитайте, количество вершин в неявном суффиксном дереве строки s.
Входные данные
В первой строке записано целое число k (1 ≤ k ≤ 10^9). Во второй строке записана строка t (1 ≤ |t| ≤ 10^5). Строка t состоит только из маленьких латинских букв.
Выходные данные
Выведите единственное целое число — количество вершин в неявном суффиксном дереве строки s.
Пример
Входные данные #1
1000 a
Выходные данные #1
2