P1659 [CTT] Cheerleading Rehearsal

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$.

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 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$.

### 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 Test point | $1 \le n \le$ | $1 \le K \le$ -|-|- $1$ | $10$ | $10$ $2\sim3$ | $100$ | $100$ $4\sim7$ | $1000$ | $1000$ $8$ | $10^5$ | $1$ $9\sim11$ | $10^5$ | $10^5$ $12\sim14$ | $10^5$ | $10^{12}$ $15\sim17$ | $5\times 10^5$ | $10^{12}$ $18$ | $10^6$ | $1$ $19$ | $10^6$ | $10^6$ $20$ | $10^6$ | $10^{12}$ Translated by ChatGPT 5