当前没有测试数据。

题目描述

在上次准备 CSP 2077 的初赛模拟题时，西西已经发现了小朋友们的做题规律，这次她想戏耍一下这些不认真做题的小朋友。

具体来说，她先设定了一个字符串 $S$，然后再出 $N$ 道试题，并希望 $S$ 在其中出现的频率尽可能高。

但这里出现的频率，是按可重叠的子串来统计的，而非之前《最优模式串》中的“答案模式串”。

换句话说，她需要构造一个长度为 $N$ 的字符串，使得 $S$ 作为子串出现的次数最多，找到并输出这一次数。

输入格式

第一行一个整数 $N$，表示题目的数量。 第二行一个字符串 $S$，表示预先设定的子串。

输出格式

输出一行，一个整数，表示最优试题串中 $S$ 作为子串出现的次数。

样例

【样例 1 输入】

5
AAA

【样例 1 输出】

3

【样例 1 解释】

将每道试题的答案都设定为 'A'，题目答案串 $T$ = "AAAAA"，这样 $S$="AAA" 作为 $T$ 的子串共出现了 $3$ 次，是最优情况。

【样例 2 输入】

19
ECDEBAFECD

【样例 2 输出】

2

【样例 2 解释】

答案串可以设为 "ECDEBAFECDEBAFECDAA"

【样例 3/4】

见附加文件pattern.zip

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le N \le 10^9$，$1 \le |S| \le 10^6$，字符串 $S$ 中仅包含 'A' 到 'F' 之间的大写字母。