P16122 [USTCPC 2026] Junction and Run Code

Today, Cruskal-chan is once again troubled by a strange string problem. A junior next to her tilts their head: “Aren’t you the best at this kind of problem, senior?” Cruskal-chan blushes slightly: “Hmph, hmph! Of course it can’t stump me!”

A **run** of a string is defined as a non-empty substring that contains only one character and cannot be extended. For example, `aabaa` has three runs: `aa`, `b`, `aa`. Given a string of length $n$, you may cut it into three non-empty strings and then concatenate them in any order to form a new string. Compute how many different plans can make the number of runs in the new string equal to $k$. Note: Two plans are different if and only if the cut positions are different or the concatenation order is different. There are $6$ possible concatenation orders.

**This problem contains multiple test cases.** First, input one line containing an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. For each test case, first input one line containing two integers, which are the string length $n$ ($3 \le n \le 10^5$) and the number of runs $k$ ($1 \le k \le n$). Then input one line containing a string of length $n$, consisting only of lowercase English letters. It is guaranteed that $\sum n \le 10^5$.

Output $T$ lines, each containing one integer, the number of plans.

In the first sample, cut the string into three parts: `abb`, `cc`, `aba`. Move the third part to the front to get `abaabbcc`. The number of runs is $5$, which satisfies the requirement. Translated by ChatGPT 5