测试数据来自 system/1896

背景

明月高楼 无言一声叹
三年离合悲欢 只为一朝东流水
俯仰一世间 叹人生如梦
又逢群芳凋谢 黯然神伤独自怜

描述

Ninian 所在的神殿遭到了不明的袭击。

袭击者必须要构造出神殿的秘钥 S 才可能进入神殿。
已知一个字符串 T 。
袭击者要操作一个串 R ，初始 R 为空串，每一次操作可以在串 R 末端加入一个 T 的子串。
当 R 与 S 相同时袭击者就可以进入神殿了。

Ninian 希望拖延尽可能多的时间，所以你需要构造出一个长度为 N 的字符串 S ，使得袭击者需要进行的操作数最多。

R, S, T 都只能包含 ABCD 四个字母。

格式

输入格式

第一行一个整数 N 。
第二行一个仅含大写字母的字符串 T 。

输出格式

袭击者最多需要进行的操作数。

样例1

样例输入1

5
ABCCAD

样例输出1

5

样例2

样例输入2

5
AAABACADBABBBCBDCACBCCCDDDBDCDD

样例输出2

4

限制

对于10%的数据 1<= N, |T| <= 1000

对于60%的数据：1 <= N <= 10^5

对于 100% 的数据：
1 <= N <= 10^18
1 <= |T| <= 100000

提示

样例解释1:
S="AAAAA"

2:
S="DADDA"

来源

布吉岛。