分数: 600 点
问题陈述
给你一个字符串 S 长度 N 由字符组成 A, B,和 C.
考虑在以下时间之间执行以下操作 0 和 K 次,包括:
- 自由选择两个角色 S 并交换它们。
查找满足以下条件的字符串数: S 可以在运算之后,取模 998244353.
约束
- 1 \leq N \leq 250000
- 1 \leq K \leq 100
- S 是一个长度为 N 由字符组成
A,B,和C. - 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K S
输出
打印答案。
示例输入 1
3 1 ABC
示例输出 1
4
可以得到以下四个字符串:
- S=
ABC:无需任何操作。 - S=
BAC: 交换 1-st 和 2-nd 字符。 - S=
CBA: 交换 1-st 和 3-rd 字符。 - S=
ACB: 交换 2-nd 和 3-rd 字符。
示例输入 2
3 2 ABC
示例输出 2
6
示例输入 3
4 5 AAAA
示例输出 3
1
示例输入 4
30 10 CACCABAABBABABBCBBCAAACAAACCCA
示例输出 4
42981885