The condition for a string \(T\) to be a “good string” is that the parities of the counts of A, B, and C in \(T\) all match.

Next, let’s consider counting the number of contiguous substrings in a string that are “good strings.” For a string \(S\), if we compute the cumulative counts of each character from the beginning, the condition for the substring from the \(l\)-th to the \(r\)-th character to be a good string is that the differences between the cumulative counts up to the \(r\)-th character and up to the \((l-1)\)-th character are all even for all characters or all odd.

From this, we only need to know the parity of the cumulative counts, not the actual counts themselves. Furthermore, for example, if the cumulative sum states (even, even, even) and (odd, odd, odd) appear \(s\) times in total, then there are \(s(s-1)/2\) good substrings. The same applies to other states.

Therefore, if we classify substrings based on the parity state of the cumulative sums of A, B, and C and count how many times each state appears, that’s sufficient. However, there are \(2^3=8\) possible states. But since states that are inverses of each other can be considered the same, for example, if we keep track of the parity of (A count - B count) and (A count - C count), then there are only \(4\) states to consider, and counting the occurrences of each is sufficient. (Alternatively, by assigning \(1, 2, 3\) to A, B, C, and considering the cumulative XOR, we can classify the states similarly.)

Moreover, for a string of length \(N\), the total number of occurrences of all states is \(N+1\), so it’s sufficient to count only \(3\) of them, and we can perform DP using these states as indices. Specifically, we can use a DP table defined as follows. The computational complexity is \(O(N^4)\).

\(dp[i][x][a][b][c]\) = the number of strings where, after looking at the first \(i\) characters, the cumulative sum state is \(x\), and the cumulative sum states \(1,2,3\) have appeared \(a,b,c\) times, respectively.

Here, we arbitrarily assign numbers \(0,1,2,3\) to the parity states of the cumulative sums.

Finally, from the number of times each state appears, we can compute the number of good substrings, and we sum up the counts of strings where this number is at least \(K\).

Sample implementation: https://atcoder.jp/contests/arc188/submissions/60033005