CF461E.Appleman and a Game

Appleman and Toastman like games. Today they play a game with strings with the following rules. Firstly Toastman tells Appleman two strings s and t both consisting only of letters 'A', 'B', 'C', 'D'. Then Appleman must build string s as quickly as possible. Initially he has empty string, and in one second he can append to end of the current string any contiguous substring of t.

Now, Toastman and Appleman are beginning to play the game. Toastman has already told string t to Appleman, but he hasn't come up with string s yet. Toastman only thinks, that he should choose string s consisting of n characters. Of course, he wants to find the worst string for Appleman (such string, that Appleman will spend as much time as possible during the game). Tell Toastman, how much time will Appleman spend during the game if Toastman finds the worst string for him. You can assume that Appleman plays optimally, therefore he builds any string s in minimal possible time.

Appleman 和 Toastman 喜欢玩游戏。今天，他们玩一个关于字符串的游戏，规则如下：首先，Toastman 告诉 Appleman 两个字符串 $s$ 和 $t$，它们均由字母 'A'、'B'、'C'、'D' 组成。接着，Appleman 必须尽快构造出字符串 $s$。初始时他拥有一个空字符串，且每秒钟他可以将 $t$ 的任意一个连续子串追加到当前字符串的末尾。

现在，Toastman 和 Appleman 开始进行这个游戏。Toastman 已经将字符串 $t$ 告知了 Appleman，但他尚未想好字符串 $s$。Toastman 只知道，他应当选择一个长度为 $n$ 的字符串 $s$。当然，他希望找出对 Appleman 来说最“糟糕”的字符串（即 Appleman 在游戏中耗时最长的字符串）。请告诉 Toastman：若他找到了这样的最糟糕字符串 $s$，Appleman 在游戏中将花费多少时间？你可以假设 Appleman 总是采取最优策略，因此他总能以最少的可能时间构造出任意给定的字符串 $s$。

The first line contains an integer n (1 ≤ n ≤ 1018). The second line contains string t (1 ≤ |t| ≤ 105). String t consists of only letters 'A', 'B', 'C', 'D'. Each letter appears at least once in string t.

第一行包含一个整数 $n$（$1 \leq n \leq 10^{18}$）。
第二行包含一个字符串 $t$（$1 \leq |t| \leq 10^5$）。字符串 $t$ 仅由字母 'A'、'B'、'C'、'D' 组成，且每个字母在 $t$ 中至少出现一次。

Print a single integer — the largest possible time Appleman needs.

输出一个整数——Appleman 所需的最大可能时间。

In the first example, Toastman can choose s equal to "AAAAA".

In the second example, Toastman can choose s equal to "DADDA".

在第一个例子中，Toastman 可以选择 $ s $ 为 “AAAAA”。

在第二个例子中，Toastman 可以选择 $ s $ 为 “DADDA”。