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

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

Вхідні дані

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

Вихідні дані

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