题目描述

给定一个由 A、B、C 组成的长度为 $N$ 的字符串 $S$。

你可以进行如下操作 $0$ 次或至多 $K$ 次：

• 任意选择 $S$ 中的两个字符，交换它们。

请你求出经过操作后，可能得到的不同字符串的数量，对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $S$

输出格式

请输出答案。

样例 1

输入

3 1
ABC

输出

4

样例 2

输入

3 2
ABC

输出

6

样例 3

输入

4 5
AAAA

输出

1

样例 4

输入

30 10
CACCABAABBABABBCBBCAAACAAACCCA

输出

42981885

说明/提示

限制条件

• $1 \leq N \leq 250000$
• $1 \leq K \leq 100$
• $S$ 是由 A、B、C 组成的长度为 $N$ 的字符串。
• 输入的所有值均为整数。

样例解释 1

可以得到如下 $4$ 种字符串。

• $S =$ABC ：不进行操作即可。
• $S =$BAC ：交换第 $1$ 和第 $2$ 个字符即可。
• $S =$CBA ：交换第 $1$ 和第 $3$ 个字符即可。
• $S =$ACB ：交换第 $2$ 和第 $3$ 个字符即可。

由 ChatGPT 4.1 翻译