时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$。定义字符串 $t$ 为将 $s$ 循环左移 $k$ 位 $^\ddagger$ 后得到的新字符串。

请计算有多少个位置 $i$ 满足 $s[i] = t[i]$。

循环左移 $k$ 位 $^\ddagger$：如果序列为 $X=[x_1,\dots,x_p]$，则变为 $X^{\prime}=[x_2,\dots,x_p,x_1]$，称该操作为循环左移一位。执行上述操作 $k$ 次即为循环左移 $k$ 位。

格式

输入格式

第一行包含两个整数 $n$ 和 $k$，表示字符串 $s$ 的长度和循环移位数。

第二行包含一个字符串 $s$，具体含义见题目描述。

输出格式

输出满足 $s[i] = t[i]$ 的位置总数。

样例

样例输入 #1

6 2
ABABAA

样例输出 #1

4

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le k \le 10^{18}$，$s$ 仅由大写英文字母组成。