Description

不过小埋很快发现了项链的神奇之处。

我们把项链看作一个$n$元环，记作$s$，环上每个结点由大写'A'-'Z'中的一个字母组成。小埋惊奇的发现，环上有很多回文串！我们定义回文串为环上一个首尾不重叠的连续子串（即环上每个结点最多被使用一次），且满足存在一个回文中心$i$，使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。

现在，小埋给出你这个环，并希望知道有多少长度为$l$的本质不同的回文串；我们认为两个回文串本质不同，当且仅当它们回文中心所在结点不同。

Input Format

第一行，两个数表示$n$，$l$；

接下来一行读入连续的$n$个字母，分别表示$s_1$，$s_2$，…，$s_n$；其中$s_i$与$s_i$ $_{mod}$ $_{n+1}$相邻。

Output Format

一行，表示长度为$l$的回文串的个数。

16 1
XIAOMAITAIBANGLE

16

4 3
ABAB

4

Hint

本题每个测试点时限500ms

对于$30$%的数据，$n<=20$；

对于$50$%的数据，$n<=200$；

对于$80$%的数据，$n<=2000$；

对于$100$%的数据，$n<=10^6$，$0<l<=n$且$l$为奇数。

仔细读题，本题回文串与传统意义上的回文串不同。