拉拉队排练

题目描述

$n$ 个女生从左到右排成一行，每个人手中的牌子上写着一个小写英文字母。

如果一段连续区间包含奇数个女生，且区间中的字母从左到右与从右到左读完全相同，就称它为一个和谐小群体。

找出所有和谐小群体，将它们的长度按降序排列。求前 $K$ 个长度的乘积对 $19930726$ 取模的结果。如果和谐小群体的总数少于 $K$，输出 $-1$。

输入格式

第一行包含两个正整数 $n,K$。

第二行包含一个长度为 $n$ 的小写英文字母串，表示从左到右的牌子。

输出格式

输出前 $K$ 个和谐小群体长度的乘积对 $19930726$ 取模的结果；若数量不足 $K$，输出 $-1$。

样例输入 1

5 3
ababa

样例输出 1

45

样例解释

长度降序后，前三个和谐小群体的长度为 $5,3,3$，乘积为 $45$。

数据范围

• $1\le n\le 10^6$；
• $1\le K\le 10^{12}$；
• 字符串只包含小写英文字母。