#4180. 字符串计数

内存限制:128 MiB 时间限制:10 Sec

题目描述

SD有一名神犇叫做Oxer,他觉得字符串的题目都太水了,于是便出了一道题来虐蒟蒻yts1999。
他给出了一个字符串T,字符串T中有且仅有4种字符 'A', 'B', 'C', 'D'。现在他要求蒟蒻yts1999构造一个新的字符串S,构造的方法是:进行多次操作,每一次操作选择T的一个子串,将其加入S的末尾。
对于一个可构造出的字符串S,可能有多种构造方案,Oxer定义构造字符串S所需的操作次数为所有构造方案中操作次数的最小值。
Oxer想知道对于给定的正整数N和字符串T,他所能构造出的所有长度为N的字符串S中,构造所需的操作次数最大的字符串的操作次数。
蒟蒻yts1999当然不会做了,于是向你求助。

输入格式

第一行包含一个整数N,表示要构造的字符串长度。
第二行包含一个字符串T,T的意义如题所述。

输出格式

输出文件包含一行,一个整数,为你所求出的最大的操作次数。

样例

样例输入


			
5
ABCCAD

样例输出


			
5

数据范围与提示

【样例说明】


例如字符串"AAAAA",该字符串所需操作次数为5,不存在能用T的子串构造出的,且所需操作次数比5大的字符串。


【数据规模和约定】

对于100%的数据,1 ≤ N ≤ 10^18,1 ≤ |T| ≤ 10^5。