Problem Statement

You are given a string S of length N consisting of the characters A, B, and C.
Consider performing the following operation between 0 and K times, inclusive:

• Freely choose two characters in S and swap them.

Find the number of strings that S can be after the operations, modulo 998244353.

Input

The input is given from Standard Input in the following format:
N K
S

Output

Print the answer.

Constraints

• $1 \leq N \leq 250000$
• $1 \leq K \leq 100$
• S is a string of length N consisting of the characters A, B, and C.
• All input values are integers.

Sample Input 1

3 1
ABC

Sample Output 1

4

The following four strings can be obtained:

• S=ABC: No operation is needed.
• S=BAC: Swap the 1-st and 2-nd characters.
• S=CBA: Swap the 1-st and 3-rd characters.
• S=ACB: Swap the 2-nd and 3-rd characters.

Sample Input 2

3 2
ABC

Sample Output 2

6

Sample Input 3

4 5
AAAA

Sample Output 3

1

Sample Input 4

30 10
CACCABAABBABABBCBBCAAACAAACCCA

Sample Output 4

42981885

见题面 Input 部分

见题面 Output 部分