Appleman 和 Toastman 喜欢游戏。今天他们玩一个带绳子的游戏,规则如下。首先,Toastman 告诉 Appleman 两个字符串 s 和 t,都只包含字母“A”、“B”、“C”、“D”。那么 Appleman 必须尽快构建 string s。最初他有空字符串,在一秒钟内他可以将 t 的任何连续子字符串附加到当前字符串的末尾。
现在,Toastman 和 Appleman 开始玩游戏。 Toastman 已经将字符串 t 告诉了 Appleman,但他还没有想出字符串 s。 Toastman 只认为,他应该选择由 n 个字符组成的字符串 s。当然,他想为Appleman找到最差的字符串(这样的字符串,Appleman在游戏过程中会花费尽可能多的时间)。告诉 Toastman,如果 Toastman 找到对他来说最差的字符串,Appleman 将在游戏中花费多少时间。您可以假设 Appleman 演奏得最佳,因此他在尽可能短的时间内构建了任何字符串 s。
输入
第一行包含一个整数 n (1 ≤ n ≤ 1018)。第二行包含字符串 t (1 ≤ |t| ≤ 105)。字符串 t 仅包含字母“A”、“B”、“C”、“D”。每个字母在字符串 t 中至少出现一次。
输出
打印一个整数——Appleman 需要的最大可能时间。
示例
输入 #1
5 ABCCAD
输出 #1
5
输入 #2
5 AAABACADBABBBCBDCACBCCCDDDBDCDD
输出 #2
4
注意
在第一个示例中,Toastman 可以选择 s 等于“AAAAA”。
在第二个示例中,Toastman 可以选择等于“DADDA”的 s。