← 返回题目列表

AtCoder · arc168_c

C. 交换字符

中文机器翻译题面 查看原题

分数: 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