Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
A
, B
, C
からなる長さ N の文字列 S が与えられます.
以下の操作を 0 回以上 K 回以下行うことを考えます.
- S 内の 2 文字を自由に選び,入れ替える.
操作後の S としてあり得る文字列が何通りあるかを 998244353 で割ったあまりを求めてください.
制約
- 1 \leq N \leq 250000
- 1 \leq K \leq 100
- S は
A
,B
,C
からなる長さ N の文字列. - 入力される値はすべて整数.
入力
入力は以下の形式で標準入力から与えられる.
N K S
出力
答えを出力せよ.
入力例 1
3 1 ABC
出力例 1
4
以下のように 4 通りの文字列が得られます.
- S=
ABC
: 0 回の操作を行えばよい. - S=
BAC
: 1,2 文字目を入れ替える操作を行えばよい. - S=
CBA
: 1,3 文字目を入れ替える操作を行えばよい. - S=
ACB
: 2,3 文字目を入れ替える操作を行えばよい.
入力例 2
3 2 ABC
出力例 2
6
入力例 3
4 5 AAAA
出力例 3
1
入力例 4
30 10 CACCABAABBABABBCBBCAAACAAACCCA
出力例 4
42981885
Score : 600 points
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
, andC
. - All input values are integers.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the answer.
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