C - Swap Characters Editorial /

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

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