Description

The Ailiston Business School basketball team is going to compete in the annual city basketball tournament. The cheerleading squad is a highlight of the game; a good squad can often boost morale and help the team win. As the captain of the cheerleading squad, Chu Yuxin knows how important it is to train the squad well.

The selection is over. With the choices made by Yuxin and the principal, $n$ girls with excellent figures and dance skills have been chosen from many applicants. These girls will stand with the basketball team and cheer for Ailiston.

On a sunny morning, Yuxin led the team to start rehearsal. The $n$ girls line up from left to right. Each girl holds a sign bearing one of the $26$ lowercase letters, which they will wave during the game.

Yuxin notices that if a contiguous segment of girls has an odd number of members, and the letters on their signs read the same from left to right and from right to left, then this segment is called a harmonious group.

Now Yuxin wants to find all harmonious groups. After sorting them by the number of girls in descending order, what is the product of the sizes of the first $K$ harmonious groups? Since the answer can be large, please report the remainder when divided by $19930726$.

Input Format

The first line contains two positive integers $n$ and $K$, as described above.

The second line contains $n$ characters, representing the letters on the signs from left to right.

Output Format

Output a single integer: the remainder of the product described in the statement divided by $19930726$. If the total number of harmonious groups is less than $K$, output $-1$.

5 3
ababa

45

Hint

Sample Explanation

After sorting the letters of harmonious groups from left to right by group size in descending order, they are ababa, aba, aba, bab, a, a, a, b, b. The product of the first three lengths is $5 \times 3 \times 3 = 45$.

Constraints

Translated by ChatGPT 5