E. Яблов и игра
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яблов и Тостов любят играть. Сегодня они играют со строками по следующим правилам. Сперва Тостов называет Яблову две строки s и t, состоящие исключительно из букв 'A', 'B', 'C', 'D'. Затем Яблов должен как можно быстрее получить строку s. Изначально у него есть пустая строка, за одну секунду он может дописать к концу текущей строки любую непрерывную подстроку строки t.

И вот Тостов и Яблов начинают играть в описанную игру. Тостов уже назвал Яблову строку t, а вот строку s он еще не придумал. Тостов считает, что строка s должна состоять из n символов. Конечно, он хочет придумать самую плохую строку для Яблова (такую, что Яблов проведет как можно больше времени, получая ее). Скажите Тостову, сколько времени Яблов проведет за игрой, если Тостов найдет для него самую худшую строку длины n? Считайте, что Яблов всегда действует оптимально и получает любую строку s за минимально возможное время.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 1018). Во второй строке записана строка t (1 ≤ |t| ≤ 105). Строка t состоит только из букв 'A', 'B', 'C', 'D'. Каждая буква встречается в строке t хотя бы раз.

Выходные данные

Выведите единственное целое число — максимальное возможное время, необходимое Яблову, чтобы получить какую-то строку s длины n.

Примеры
Входные данные
5
ABCCAD
Выходные данные
5
Входные данные
5
AAABACADBABBBCBDCACBCCCDDDBDCDD
Выходные данные
4
Примечание

В первом примере Тостов может выбрать строку «AAAAA».

Во втором примере Тостов может выбрать строку «DADDA».