Задачі
Вершини неявного суфіксного дерева
Вершини неявного суфіксного дерева
Суфіксне дерево — називається неявним, якщо воно містить як неявний бор усі суфікси рядка і при цьому містить мінімальну кількість вершин. Наприклад, неявне суфіксне дерево рядка "ababa" виглядає так, як показано на рисунку нижче (у ньом є 3 вершини):
Вам задано рядок s
, як конкатенацію k
копій рядка t
. Тобто, . Порахуйте кількість вершин у неявному суфіксному дереві рядка s
.
Вхідні дані
У першому рядку записано ціле число k
(1 ≤ k ≤ 109
). У другому рядку записано рядок t
(1 ≤ |t| ≤ 10). Рядок t
складається лише з маленьких латинських букв.
Вихідні дані
Виведіть єдине ціле число — кількість вершин у неявному суфіксному дереві рядка s
.
Вхідні дані #1
1000 a
Вихідні дані #1
2