eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 256 MiB

Суффиксное дерево — называется неявным, если оно содержит как неявный бор все суффиксы строки и при этом содержит минимальное количество вершин.

Например, неявное суффиксное дерево строки "ababa" выглядит так, как показано на рисунке ниже (в нем имеются 3 вершины):

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

Input data

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

Output data

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

Examples

Input example #1
1000
a
Output example #1
2