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

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.

Input

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

N K
S

Output

Print the answer.