Migrated from Lutece 2861 摸鱼

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

PESTC 有一个条形的池塘，很多人都在这个池塘旁边摸鱼。现在有 $n$ 个人在摸鱼，从左到右分别编号为 $1$ 到 $n$。每个人的摸鱼方式用一个小写英文字母表示，如果以某个人为中点的一段连续的人，所有关于位于中间的那个人对称的两个人摸鱼方式一样，那么这段人就看起来很摸，摸鱼度就是这段人的人数。注意，每个人都在摸鱼，所以单个人也看起来很摸，摸鱼度为 $1$。

Kanade 想知道，前 $k$ 大摸鱼度的乘积是多少。如果有少于 $k$ 段人看起来很摸，输出 $-1$。

Input

第一行两个整数 $n,k\ (1\le n\le 10^5, 1\le k\le \frac{n(n+1)}{2})$，意义如题目描述。

第二行一个长为 $n$ 且由小写英文字母构成的字符串。

Output

如果有少于 $k$ 段人看起来很摸，输出 $-1$，否则输出一行一个整数，表示前 $k$ 大摸鱼度的乘积。由于答案过大，请输出这个乘积对 $10^9+7$ 取模后的值。

Samples

5 3
ababa

45

4 3
abba

1

Note

样例 1 中，所有看起来很摸的连续一段人按摸鱼度从大到小排序后为：

• $\texttt{ababa}$
• $\texttt{aba}$
• $\texttt{aba}$
• $\texttt{bab}$
• $\texttt{a}$
• $\texttt{a}$
• $\texttt{a}$
• $\texttt{b}$
• $\texttt{b}$

答案为 $5\times 3\times 3\bmod (10^9+7)=45$。

样例 2 中，所有看起来很摸的连续一段人按摸鱼度从大到小排序后为：

• $\texttt{a}$
• $\texttt{a}$
• $\texttt{b}$
• $\texttt{b}$

注意 $\texttt{abba}$ 并不是看起来很摸的连续一段人，$\texttt{aba}$ 不是连续的一段人。

答案为 $1\times 1\times 1\bmod (10^9+7)=1$。

Resources

The 19th UESTC Programming Contest Preliminary