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

Суфіксне дерево називається неявним, якщо воно містить усі суфікси рядка у вигляді неявного бору, при цьому маючи мінімальну кількість вершин.

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

Вам дано рядок s, що є конкатенацією k копій рядка t. Тобто, s = t + t + t + ... + t. Порахуйте кількість вершин у неявному суфіксному дереві рядка s.

Вхідні дані

У першому рядку задано ціле число k (1 ≤ k ≤ 10^9). У другому рядку задано рядок t (1 ≤ |t| ≤ 10^5). Рядок t складається лише з малих латинських літер.

Вихідні дані

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

Приклади