Вершини неявного суфіксного дерева (Hard)#5943
Суфіксне дерево називається неявним, якщо воно містить усі суфікси рядка у вигляді неявного бору, при цьому маючи мінімальну кількість вершин.
Наприклад, неявне суфіксне дерево для рядка "" виглядає так, як показано на рисунку нижче (воно містить вершини):
Вам дано рядок , що є конкатенацією копій рядка . Тобто, s = t + t + t + \ldots + t. Порахуйте кількість вершин у неявному суфіксному дереві рядка .
У першому рядку задано ціле число (1 \le k \le 10^9). У другому рядку задано рядок (1 \le |t| \le 10^5). Рядок складається лише з малих латинських літер.
Виведіть єдине ціле число — кількість вершин у неявному суфіксному дереві рядка .
Приклад 1