字符串计数
题目描述
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。