C - Swap Characters
Source: atcoder
Difficulty: 600

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

C++ solution:
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 2.5e5 + 1, mod = 998244353;

int n, k, K, o[3];
string s;
ll c[kMaxN], y[kMaxN], Y[kMaxN], ans, u, t;

inline ll C(int n, int m) { return c[n] * Y[n - m] % mod * Y[m] % mod; }

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k >> s, c[0] = Y[0] = y[1] = 1;
  for (int i = 1; i <= n; i++) {
    c[i] = c[i - 1] * i % mod, i > 1 && (y[i] = mod - mod / i * y[mod % i] % mod), Y[i] = Y[i - 1] * y[i] % mod, o[s[i - 1] - 'A']++;
  }
  for (int i = 0; i <= min({k, o[0], n / 2}); i++) {
    K = k - i;
    for (int j = 0; j <= min(i, o[1]); j++) {
      if (i - j <= o[2]) {
        u = 0;
        for (int l = 0; l <= min({K, j, o[2] - (i - j)}); l++) {
          t = 0;
          for (int p = 0; p <= min({K - l, o[1] - j, o[2] - (i - j) - l}); p++) {
            t = (t + C(o[1] - j, p) * C(o[2] - (i - j), p + l)) % mod;
          }
          u = (u + t * C(i, j - l)) % mod;
        }
        for (int l = 1; l <= min({K, i - j, o[1] - j}); l++) {
          t = 0;
          for (int p = 0; p <= min({K - l, o[1] - j - l, o[2] - (i - j)}); p++) {
            t = (t + C(o[1] - j, l + p) * C(o[2] - (i - j), p)) % mod;
          }
          u = (u + t * C(i, j + l)) % mod;
        }
        ans = (ans + u * C(o[1], j) % mod * C(o[2], i - j) % mod * C(o[0], i)) % mod;
      }
    }
  }
  cout << ans;
  return 0;
}

Go solution:
package main

import (
	"bufio"
	"container/heap"
	"container/list"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	// "github.com/emirpasic/gods/trees/redblacktree"
)

// const mod = 1000000007

const mod = 998244353

var sc = bufio.NewScanner(os.Stdin)

func main() {
	buf := make([]byte, bufio.MaxScanTokenSize)
	sc.Buffer(buf, 1000*1000)
	sc.Split(bufio.ScanWords)

	n, k, s := ni(), ni(), ns()
	c := make([]int, 3)
	for i := 0; i < n; i++ {
		c[s[i]-'A']++
	}

	cf := newcombFactorial(n + 1)

	res := 0
	// x: A<->B, y: B<->C, z: C<->A, w: A->B->C->A
	for w := 0; 2*w <= k; w++ {
		for x := 0; x <= k; x++ {
			if x+w > c[0] || x+2*w > k {
				break
			}
			for y := 0; y <= k; y++ {
				if y+w > c[1] || x+y+2*w > k {
					break
				}
				for z := 0; z <= k; z++ {
					if z+w > c[2] || x+y+z+2*w > k {
						break
					}
					res += cf.combination(c[0], x+w) * cf.combination(c[0]-x-w, z) % mod *
						cf.combination(c[1], y+w) % mod * cf.combination(c[1]-y-w, x) % mod *
						cf.combination(c[2], z+w) % mod * cf.combination(c[2]-z-w, y) % mod
					res %= mod
					if w != 0 {
						res += cf.combination(c[0], x) * cf.combination(c[0]-x, z+w) % mod *
							cf.combination(c[1], y) % mod * cf.combination(c[1]-y, x+w) % mod *
							cf.combination(c[2], z) % mod * cf.combination(c[2]-z, y+w) % mod
						res %= mod
					}
				}
			}
		}
	}
	fmt.Println(res)
}

// ==================================================
// io
// ==================================================

func ni() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nf() float64 {
	sc.Scan()
	f, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func ns() string {
	sc.Scan()
	return sc.Text()
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

// ==================================================
// math
// ==================================================
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func chmin(a *int, b int) {
	if *a > b {
		*a = b
	}
}
func chmax(a *int, b int) {
	if *a < b {
		*a = b
	}
}
func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func maxf(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}
func minf(a, b float64) float64 {
	if a < b {
		return a
	}
	return b
}
func chminf(a *float64, b float64) {
	if *a > b {
		*a = b
	}
}
func chmaxf(a *float64, b float64) {
	if *a < b {
		*a = b
	}
}
func absf(a float64) float64 {
	if a > 0 {
		return a
	}
	return -a
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

// ==================================================
// sort
// ==================================================

func sorti(sl []int) {
	sort.Sort(sort.IntSlice(sl))
}

func sortir(sl []int) {
	sort.Sort(sort.Reverse(sort.IntSlice(sl)))
}

func sorts(sl []string) {
	sort.Slice(sl, func(i, j int) bool {
		return sl[i] < sl[j]
	})
}

// ==================================================
// slice
// ==================================================

func initslice(len int, def int) []int {
	sl := make([]int, len)
	for i := 0; i < len; i++ {
		sl[i] = def
	}
	return sl
}

func initslice2(x, y int, def int) [][]int {
	sl := make([][]int, x)
	for i := 0; i < x; i++ {
		sl[i] = initslice(y, def)
	}
	return sl
}

// ==================================================
// mod
// ==================================================
func madd(a, b int) int {
	a += b
	if a >= mod || a <= -mod {
		a %= mod
	}
	if a < 0 {
		a += mod
	}
	return a
}

func mmul(a, b int) int {
	return a * b % mod
}

func mdiv(a, b int) int {
	a %= mod
	return a * minvfermat(b, mod) % mod
}

func mpow(a, n, m int) int {
	if m == 1 {
		return 0
	}
	r := 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % m
		}
		a, n = a*a%m, n>>1
	}
	return r
}

func minv(a, m int) int {
	p, x, u := m, 1, 0
	for p != 0 {
		t := a / p
		a, p = p, a-t*p
		x, u = u, x-t*u
	}
	x %= m
	if x < 0 {
		x += m
	}
	return x
}

// m only allow prime number
func minvfermat(a, m int) int {
	return mpow(a, m-2, mod)
}

// ==================================================
// union find
// ==================================================

type UnionFind struct {
	par []int
}

/*
// 使い方
// インスタンスの生成
u := newUnionFind(N)

// 各メソッドの利用
u.unite(a, b)
u.same(a, b)
u.size(a)
u.root(a)
*/
func newUnionFind(N int) *UnionFind {
	u := new(UnionFind)
	u.par = make([]int, N)
	for i := range u.par {
		u.par[i] = -1
	}
	return u
}

/* xの所属するグループを返す */
func (u UnionFind) root(x int) int {
	if u.par[x] < 0 {
		return x
	}
	u.par[x] = u.root(u.par[x])
	return u.par[x]
}

/* xの所属するグループ と yの所属するグループ を合体する */
func (u UnionFind) unite(x, y int) {
	xr := u.root(x)
	yr := u.root(y)
	if xr == yr {
		return
	}
	u.par[yr] += u.par[xr]
	u.par[xr] = yr
}

/* xとyが同じグループに所属するかどうかを返す */
func (u UnionFind) same(x, y int) bool {
	if u.root(x) == u.root(y) {
		return true
	}
	return false
}

/* xの所属するグループの木の大きさを返す */
func (u UnionFind) size(x int) int {
	return -u.par[u.root(x)]
}

// ==================================================
// binarysearch
// ==================================================

/*
	o = bs(0, len(sl)-1, func(c int) bool {
		return true
	})

sort.Search(n int, func(i int) bool) でも同じことができる
*/
func bs(ok, ng int, f func(int) bool) int {
	if !f(ok) {
		return -1
	}
	if f(ng) {
		return ng
	}
	for abs(ok-ng) > 1 {
		mid := (ok + ng) / 2

		if f(mid) {
			ok = mid
		} else {
			ng = mid
		}
	}

	return ok
}

// ex) 降順のsliceから, sl[x]<v を満たす最大のxを探す
// find x of sl[x] < v. return -1 if no lowerbound found
func lowerBound(v int, sl []int) int {
	if len(sl) == 0 {
		panic("slise len is zero")
	}
	idx := bs(0, len(sl)-1, func(c int) bool {
		return sl[c] < v
	})
	return idx
}

// ==================================================
// graph
// ==================================================

type edge struct {
	from int
	to   int
	cost int
	rev  int // 逆辺。最大フロー問題で使用
}

type state struct {
	node  int
	score int
}

/* n頂点を持つedgesグラフで頂点startからの距離をリストで返す。O((n+m)log n) */
func dijkstra(edges [][]edge, n, start int) []int {

	// g.starts = []state{{node: start}}

	score := make([]int, n)
	for i := 0; i < n; i++ {
		score[i] = inf
	}
	score[start] = 0

	que := newpq([]compFunc{
		func(p, q interface{}) int {
			if p.(state).score < q.(state).score {
				return -1
			} else if p.(state).score > q.(state).score {
				return 1
			} else {
				return 0
			}
		},
	})
	heap.Push(que, state{node: start, score: 0})

	for !que.IsEmpty() {
		st := heap.Pop(que).(state)
		if st.score > score[st.node] {
			continue
		}
		for _, edge := range edges[st.node] {
			newScore := st.score + edge.cost
			if score[edge.to] > newScore {
				score[edge.to] = newScore
				heap.Push(que, state{score: newScore, node: edge.to})
			}
		}
	}
	return score
}

/*
h := &OrgIntHeap{a, b, c}
heap.Init(h) 	// 使用する際にはまずInitを呼ぶ
heap.Push(h, v) // heap.Push経由で値を投入

	for !h.IsEmpty() {
		v = heap.Pop(h).(int) // heap.Pop経由で値を取り出す
	}
*/
type OrgIntHeap []int

func (h OrgIntHeap) Len() int { return len(h) }

// get from bigger
// func (h OrgIntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h OrgIntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h OrgIntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *OrgIntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *OrgIntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *OrgIntHeap) IsEmpty() bool {
	return h.Len() == 0
}

// h.Min().(int)
func (h *OrgIntHeap) Min() interface{} {
	return (*h)[0]
}

/*
	// 使い方の例
	// pqに入れるアイテムの型を定義
	type pqst struct {
		x int
		y int
	}

	pq := newpq([]compFunc{func(p, q interface{}) int {
		if p.(pqst).x != q.(pqst).x {
			// get from bigger
			// if p.(pqst).x > q.(pqst).x {
			if p.(pqst).x < q.(pqst).x {
				return -1
			} else {
				return 1
			}
		}
		if p.(pqst).y != q.(pqst).y {
			// get from bigger
			// if p.(pqst).y > q.(pqst).y {
			if p.(pqst).y < q.(pqst).y {
				return -1
			} else {
				return 1
			}
		}
		return 0
	}})

heap.Init(pq)
heap.Push(pq, pqst{x: 1, y: 1})

	for !pq.IsEmpty() {
		v := heap.Pop(pq).(pqst)
	}
*/
type pq struct {
	arr   []interface{}
	comps []compFunc
}

type compFunc func(p, q interface{}) int

func newpq(comps []compFunc) *pq {
	return &pq{
		comps: comps,
	}
}

func (pq pq) Len() int {
	return len(pq.arr)
}

func (pq pq) Swap(i, j int) {
	pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
}

func (pq pq) Less(i, j int) bool {
	for _, comp := range pq.comps {
		result := comp(pq.arr[i], pq.arr[j])
		switch result {
		case -1:
			return true
		case 1:
			return false
		case 0:
			continue
		}
	}
	return true
}

func (pq *pq) Push(x interface{}) {
	pq.arr = append(pq.arr, x)
}

func (pq *pq) Pop() interface{} {
	n := pq.Len()
	item := pq.arr[n-1]
	pq.arr = pq.arr[:n-1]
	return item
}

func (pq *pq) IsEmpty() bool {
	return pq.Len() == 0
}

// pq.GetRoot().(edge)
func (pq *pq) GetRoot() interface{} {
	return pq.arr[0]
}

// ==================================================
// SCC (強連結成分分析)
// ==================================================
// step1 DFSで深い順にorderに追加
// step2 枝の方向を逆転し、orderの逆順にDFS
//
// 使い方
// n: 頂点数, edges: edgeの集合, r_edges: 反転したedgeの集合
// returns: 強連結成分ごとの頂点集合
func scc(n int, edges, r_edges [][]edge) [][]int {

	// step1
	order := []int{}
	used := make([]bool, n)

	var dfs func(v int)
	dfs = func(v int) {
		used[v] = true
		for _, next := range edges[v] {
			if !used[next.to] {
				dfs(next.to)
			}
		}
		order = append(order, v)
	}
	for v := 0; v < n; v++ {
		if !used[v] {
			dfs(v)
		}
	}

	// step2
	scc := [][]int{}
	used = make([]bool, n)

	var rdfs func(v, k int)
	rdfs = func(v, k int) {
		used[v] = true
		scc[k] = append(scc[k], v)
		for _, next := range r_edges[v] {
			if !used[next.to] {
				rdfs(next.to, k)
			}
		}
	}
	k := 0
	for i := n - 1; i >= 0; i-- {
		v := order[i]
		if !used[v] {
			scc = append(scc, []int{})
			rdfs(v, k)
			k++
		}
	}

	return scc
}

// ==================================================
// combination
// ==================================================
//
// 使い方
// c := newcombFactorial(n)
// nCr = c.combination(n,r)  *mod後のinteger

type combFactorial struct {
	fac    []int
	facinv []int
}

func newcombFactorial(n int) *combFactorial {

	fac := make([]int, n)
	facinv := make([]int, n)
	fac[0] = 1
	facinv[0] = minvfermat(1, mod)

	for i := 1; i < n; i++ {
		fac[i] = mmul(i, fac[i-1])
		facinv[i] = minvfermat(fac[i], mod)
	}

	return &combFactorial{
		fac:    fac,
		facinv: facinv,
	}
}

func (c *combFactorial) factorial(n int) int {
	return c.fac[n]
}

func (c *combFactorial) combination(n, r int) int {
	if r > n {
		return 0
	}
	return mmul(mmul(c.fac[n], c.facinv[r]), c.facinv[n-r])
}

func (c *combFactorial) permutation(n, r int) int {
	if r > n {
		return 0
	}
	return mmul(c.fac[n], c.facinv[n-r])
}

func (c *combFactorial) homogeousProduct(n, r int) int {
	return c.combination(n-1+r, r)
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

/*
	for {
		// Do something
		if !nextPermutation(sort.IntSlice(x)) {
			break
		}
	}
*/
func nextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// ==================================================
// bit (Binary Index Tree)
// ==================================================
// newbit で長さn の配列用 treeを作成
// add(i, x) で 配列のi 番目の値をx加算
// sum(i) で配列の0-i番目までの値の累積和を計算

type bit struct {
	n int
	b []int
}

func newbit(n int) *bit {
	return &bit{
		n: n + 1,
		b: make([]int, n+1),
	}
}

func (b *bit) culc(i, j int) int {
	return i + j
	//return madd(i, j)
}

func (b *bit) add(i, x int) {
	for i++; i < b.n && i > 0; i += i & -i {
		b.b[i] = b.culc(b.b[i], x)
	}
}

func (b *bit) sum(i int) int {
	ret := 0
	for i++; i > 0; i -= i & -i {
		ret = b.culc(ret, b.b[i])
	}
	return ret
}

// ==================================================
// セグメント木（segment tree）
// ==================================================
// newstree(n,stmin|stmax|stadd|stmadd) でセグメント木を作成
// s.set(i,x)
// s.add(i,x)
// result1 := s.query(l,r)  // [l,r) の区間の値を返すことに注意

type streeculctype int

const (
	stadd streeculctype = iota
	stmadd
	stset
	stmin
	stmax
)

const inf = 1<<62 - 1

type stree struct {
	n   int
	b   []int
	def int
	cmp func(i, j int) int
}

func newstree(n int, minmax streeculctype) *stree {
	tn := 1
	for tn < n {
		tn *= 2
	}
	s := &stree{
		n: tn,
		b: make([]int, 2*tn-1),
	}
	switch minmax {
	case stmin:
		s.def = inf
		for i := 0; i < 2*tn-1; i++ {
			s.b[i] = s.def
		}
		s.cmp = func(i, j int) int {
			return min(i, j)
		}
	case stmax:
		s.cmp = func(i, j int) int {
			return max(i, j)
		}
	case stadd:
		s.cmp = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return i + j
		}
	case stmadd:
		s.cmp = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return madd(i, j)
		}
	}
	return s
}

func (s *stree) add(i, x int) {
	i += s.n - 1
	s.b[i] += x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s *stree) set(i, x int) {
	i += s.n - 1
	s.b[i] = x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s *stree) query(a, b int) int {
	return s.querysub(a, b, 0, 0, s.n)
}

func (s *stree) querysub(a, b, k, l, r int) int {
	if r <= a || b <= l {
		return s.def
	}
	if a <= l && r <= b {
		return s.b[k]
	}
	return s.cmp(
		s.querysub(a, b, k*2+1, l, (l+r)/2),
		s.querysub(a, b, k*2+2, (l+r)/2, r),
	)
}

// ==================================================
// 遅延評価セグメント木 (Lazy Segment Tree)
// ==================================================
// 区間の更新、加算を O(log n)でできるように改良したセグメント木
// s := newlazystree(n,stmin|stmax,stset|stadd|stmadd)　でインスタンス生成
// 2つ目の引数はqueryでの計算方法、3つ目の引数はupdateでの計算方法 (stsetは上書き、staddは加算、stmaddはmod加算)
//
// s.set(i,x),  s.add(i,x) は通常のセグメント木と同じ（遅延評価なし）
// s.update(l,r,x) で区間[l,r)をxで更新（遅延評価なのでこの時点ではセグメント木を更新しない）
// result1 := s.query(l,r) // [l,r) の区間の値を返すことに注意

type lazystree struct {
	on   int
	n    int
	b    []int
	lazy []int
	def  int
	cmp  func(i, j int) int
	culc func(i, j int) int
}

func newlazystree(n int, cmptype streeculctype, culctype streeculctype) lazystree {
	tn := 1
	for tn < n {
		tn *= 2
	}
	s := lazystree{
		on:   n,
		n:    tn,
		b:    make([]int, 2*tn-1),
		lazy: make([]int, 2*tn-1),
	}
	switch cmptype {
	case stmin:
		s.def = inf
		for i := 0; i < 2*tn-1; i++ {
			s.b[i] = s.def
			s.lazy[i] = s.def
		}
		s.cmp = func(i, j int) int {
			return min(i, j)
		}
	case stmax:
		s.cmp = func(i, j int) int {
			return max(i, j)
		}
	}
	switch culctype {
	case stadd:
		s.culc = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return i + j
		}
	case stmadd:
		s.culc = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return madd(i, j)
		}
	case stmax:
		s.culc = func(i, j int) int {
			return max(i, j)
		}
	case stmin:
		s.culc = func(i, j int) int {
			return min(i, j)
		}
	case stset:
		s.culc = func(i, j int) int {
			return j
		}
	}
	return s
}

func (s lazystree) eval(k int) {
	if s.lazy[k] == s.def {
		return
	}
	if k < s.n-1 {
		s.lazy[k*2+1] = s.culc(s.lazy[k*2+1], s.lazy[k])
		s.lazy[k*2+2] = s.culc(s.lazy[k*2+2], s.lazy[k])
	}
	s.b[k] = s.culc(s.b[k], s.lazy[k])
	s.lazy[k] = s.def
}

func (s lazystree) add(i, x int) {
	i += s.n - 1
	s.b[i] += x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s lazystree) set(i, x int) {
	i += s.n - 1
	s.b[i] = x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

// range culc a <= n n < b
func (s lazystree) update(a, b, x int) {
	s.rcsub(a, b, x, 0, 0, s.n)
}

func (s lazystree) rcsub(a, b, x, k, l, r int) {
	s.eval(k)
	if a <= l && r <= b {
		s.lazy[k] = s.culc(s.lazy[k], x)
		s.eval(k)
	} else if l < b && a < r {
		s.rcsub(a, b, x, k*2+1, l, (l+r)/2)
		s.rcsub(a, b, x, k*2+2, (l+r)/2, r)
		s.b[k] = s.cmp(s.b[k*2+1], s.b[k*2+2])
	}
}

func (s lazystree) get(a int) int {
	return s.query(a, a+1)
}

func (s lazystree) query(a, b int) int {
	return s.querysub(a, b, 0, 0, s.n)
}

func (s lazystree) querysub(a, b, k, l, r int) int {
	s.eval(k)
	if r <= a || b <= l {
		return s.def
	}
	if a <= l && r <= b {
		return s.b[k]
	}
	return s.cmp(
		s.querysub(a, b, k*2+1, l, (l+r)/2),
		s.querysub(a, b, k*2+2, (l+r)/2, r),
	)
}

/*
最大フロー問題を解く (Dinic法)
edges: Graph (逆辺を含む)
s: start
t: target
計算量はO(V^2 E)
*/
func maxflow(edges [][]edge, s, t int) int {
	n := len(edges)
	level := make([]int, n)
	iter := make([]int, n)
	flow := 0

	bfs := func(s int) {
		for i := 0; i < n; i++ {
			level[i] = -1
		}
		level[s] = 0
		q := list.New()
		q.PushBack(s)
		for q.Len() > 0 {
			v := q.Remove(q.Front()).(int)
			for i := 0; i < len(edges[v]); i++ {
				e := &edges[v][i]
				if e.cost > 0 && level[e.to] < 0 {
					level[e.to] = level[v] + 1
					q.PushBack(e.to)
				}
			}
		}
	}
	var dfs func(int, int, int) int
	dfs = func(v int, t int, f int) int {
		if v == t {
			return f
		}
		for i := iter[v]; i < len(edges[v]); i++ {
			iter[v] = i
			e := &edges[v][i]
			if e.cost > 0 && level[v] < level[e.to] {
				d := dfs(e.to, t, min(f, e.cost))
				if d > 0 {
					e.cost -= d
					edges[e.to][e.rev].cost += d
					return d
				}
			}
		}
		return 0
	}
	for {
		bfs(s)
		if level[t] < 0 {
			return flow
		}
		iter = make([]int, n)
		f := dfs(s, t, inf)
		for f > 0 {
			flow += f
			f = dfs(s, t, inf)
		}
	}
}

/*
	最大フロー問題の準備用

逆辺を追加する関数を作る
*/
func addEdge(edges [][]edge, from, to, cost int) {
	edges[from] = append(edges[from], edge{from, to, cost, len(edges[to])})
	edges[to] = append(edges[to], edge{to, from, 0, len(edges[from]) - 1})
}

/*
Zアルゴリズム: 文字列Sを与えてZ配列を返す。
Z[i]=S[0:]とS[i:]の先頭何文字が一致しているか？
*/
func z_algorithm(s string) []int {
	z := make([]int, len(s))
	z[0] = len(s)

	i, j := 1, 0
	for i < len(s) {
		for i+j < len(s) && s[j] == s[i+j] {
			j++
		}
		z[i] = j

		if j == 0 {
			i++
			continue
		}

		k := 1
		for k < j && k+z[k] < j {
			z[i+k] = z[k]
			k++
		}
		i += k
		j -= k
	}
	return z
}

func revstr(s string) string {
	r := []rune(s)
	for i := 0; i < len(r)/2; i++ {
		r[i], r[len(r)-i-1] = r[len(r)-i-1], r[i]
	}
	return string(r)
}

// ==================================================
// fft: 高速フーリエ変換
// ==================================================

/*
Convolution: 畳み込み
a, b: 畳み込む配列
C[i] = Σa[j]b[i-j] を O(NlogN) で求める (N=len(a)+len(b))
*/
func convolution(a, b []int) []int {
	n1, n2 := len(a), len(b)
	n := n1 + n2 - 1
	if n1 == 0 || n2 == 0 {
		return []int{}
	}

	z := 1 << ceilPow2(n)
	aa, bb := make([]int, z), make([]int, z)
	copy(aa, a)
	copy(bb, b)
	a, b = aa, bb

	butterfly(a, mod)
	butterfly(b, mod)
	for i := 0; i < z; i++ {
		a[i] = a[i] * b[i] % mod
	}
	butterflyInv(a, mod)
	a = a[:n]
	iz := minv(z, mod)
	for i := 0; i < n; i++ {
		a[i] = a[i] * iz % mod
		if a[i] < 0 {
			a[i] += mod
		}
	}

	return a
}

func primitiveRoot(m int) int {
	if m == 2 {
		return 1
	}
	if m == 167772161 || m == 469762049 || m == 998244353 {
		return 3
	}
	if m == 754974721 {
		return 11
	}
	divs := make([]int, 20)
	divs[0] = 2
	cnt := 1
	x := (m - 1) / 2
	for x%2 == 0 {
		x /= 2
	}
	for i := 3; i*i <= x; i += 2 {
		if x%i == 0 {
			divs[cnt] = i
			cnt++
			for x%i == 0 {
				x /= i
			}
		}
	}
	if x > 1 {
		divs[cnt] = x
		cnt++
	}
	for g := 2; ; g++ {
		ok := true
		for i := 0; i < cnt; i++ {
			if mpow(g, (m-1)/divs[i], m) == 1 {
				ok = false
				break
			}
		}
		if ok {
			return g
		}
	}
}

func ceilPow2(n int) int {
	x := 0
	for 1<<x < n {
		x++
	}
	return x
}

func bsf(n int) int {
	x := 0
	for n&(1<<x) == 0 {
		x++
	}
	return x
}

func butterfly(a []int, M int) {
	g := primitiveRoot(M)
	n := len(a)
	h := ceilPow2(n)

	se := make([]int, 30)
	es, ies := make([]int, 30), make([]int, 30)
	cnt2 := bsf(M - 1)
	e := mpow(g, (M-1)>>cnt2, M)
	ie := minv(e, M)
	for i := cnt2; i >= 2; i-- {
		es[i-2] = e
		ies[i-2] = ie
		e = e * e % M
		ie = ie * ie % M
	}
	now := 1
	for i := 0; i <= cnt2-2; i++ {
		se[i] = es[i] * now % M
		now = now * ies[i] % M
	}
	for ph := 1; ph <= h; ph++ {
		w := 1 << (ph - 1)
		p := 1 << (h - ph)
		now := 1
		for s := 0; s < w; s++ {
			offset := s << (h - ph + 1)
			for i := 0; i < p; i++ {
				l := a[i+offset]
				r := a[i+offset+p] * now % M
				a[i+offset] = (l + r) % M
				a[i+offset+p] = (M + l - r) % M
			}
			now = now * se[bsf(^s)] % M
		}
	}
}

func butterflyInv(a []int, M int) {
	g := primitiveRoot(M)
	n := len(a)
	h := ceilPow2(n)

	sie := make([]int, 30)
	es, ies := make([]int, 30), make([]int, 30)
	cnt2 := bsf(M - 1)
	e := mpow(g, (M-1)>>cnt2, M)
	ie := minv(e, M)
	for i := cnt2; i >= 2; i-- {
		es[i-2] = e
		ies[i-2] = ie
		e = e * e % M
		ie = ie * ie % M
	}
	now := 1
	for i := 0; i <= cnt2-2; i++ {
		sie[i] = ies[i] * now % M
		now = now * es[i] % M
	}
	for ph := h; ph >= 1; ph-- {
		w := 1 << (ph - 1)
		p := 1 << (h - ph)
		inow := 1
		for s := 0; s < w; s++ {
			offset := s << (h - ph + 1)
			for i := 0; i < p; i++ {
				l := a[i+offset]
				r := a[i+offset+p]
				a[i+offset] = (l + r) % M
				a[i+offset+p] = (M + l - r) * inow % M
			}
			inow = inow * sie[bsf(^s)] % M
		}
	}
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.util.function.IntFunction;
import java.util.function.LongFunction;

public class Main {
	public static void main(String[] args) {
		Main o = new Main();
		o.solve();
	}

	static final long MOD = 998244353;
	long[] F = null;
	long[] FI = null;
	public void solve() {
		FastScanner sc = new FastScanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();

		System.out.println(solve(N, K, S));
	}

	long solve(int N, int K, String S) {
		int[] cnt = new int[3];
		for (int i = 0; i < N; i++) {
			cnt[S.charAt(i) - 'A']++;
		}

		F = new long[N + 1];
		FI = new long[N + 1];
		F[0] = 1;
		FI[0] = 1;
		for (int i = 1; i <= N; i++) {
			F[i] = (F[i - 1] * i) % MOD;
			FI[i] = modInv(F[i], MOD);
		}

		long ans = 0;
		for (int ab = 0; ab <= K; ab++) {
			for (int bc = 0; bc <= K - ab; bc++) {
				for (int ca = 0; ca <= K - ab - bc; ca++) {
					//if ( ab != 0 && bc != 0 && ca != 0 ) continue;
					//if ( (ab + bc + ca) * 2 > N ) continue;
					int r = K - ab - bc - ca;
					for (int abc = 0; abc <= r / 2; abc++) {
						// int r2 = K - ab - bc - ca - abc * 2;
						// for (int acb = 0; acb <= r2 / 2; acb++) {
							long x = solve0(ab, bc, ca, abc, 0, cnt);
							ans = (ans + x) % MOD;
							if ( abc != 0 ) {
								long x2 = solve0(ab, bc, ca, 0, abc, cnt);
								ans = (ans + x2) % MOD;
							}
							// if (x != 0) System.out.println(String.format("%d,%d,%d,%d,%d -> %d", ab, bc, ca, abc, 0, x));
						// }
					}
				}
			}
		}
		return ans;
	}

	long solve0(int ab, int bc, int ca, int abc, int acb, int[] cnt) {
		long ret = 1;
		if ( cnt[0] < ab + ca + abc + acb || cnt[1] < ab + bc + abc + acb || cnt[2] < bc + ca + abc + acb ) return 0;
		if ( cnt[0] < ab + abc || cnt[1] < bc + abc || cnt[2] < ca + abc ) return 0;
		ret = mul(ret, C(cnt[0], ab + abc), C(cnt[0] - ab - abc, ca + acb));
		ret = mul(ret, C(cnt[1], bc + abc), C(cnt[1] - bc - abc, ab + acb));
		ret = mul(ret, C(cnt[2], ca + abc), C(cnt[2] - ca - abc, bc + acb));
		return ret;
	}

	// long P(int n, int r) {
	// 	return (F[n] * FI[n - r]) % MOD;
	// }
	long C(int n, int r) {
		return (((F[n] * FI[n - r]) % MOD) * FI[r]) % MOD;
	}
	long mul(long a, long b) {
		return (a * b) % MOD;
	}
	long mul(long a, long b, long c) {
		return (((a * b) % MOD) * c) % MOD;
	}
	long mul(long a, long b, long c, long d) {
		return (((a * b) % MOD) * ((c * d) % MOD)) % MOD;
	}

	static long modInv(long a, long p) {
		long x0 = 1;
		long y0 = 0;
		long x1 = 0;
		long y1 = 1;
		long b = p;
		while ( b != 0 ) {
			long q = a / b;
			long tmp = b;
			b = a % b;
			a = tmp;

			tmp = x1;
			x1 = x0 - q * x1;
			x0 = tmp;

			tmp = y1;
			y1 = y0 - q * y1;
			y0 = tmp;
		}

		return (x0 + p) % p;
	}

	static final char LF = '\n';
	static final char SPACE = ' ';
	static final String YES = "Yes";
	static final String NO = "No";
	void print(int[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void print(long[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void printYesNo(boolean yesno) {
		System.out.println(yesno ? YES : NO);
	}
	void printDouble(double val, int digit) {
		System.out.println(String.format("%." + digit + "f", val));
	}
	
	class FastScanner {
		private final InputStream in;
		private final byte[] buf = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		FastScanner( InputStream source ) { this.in = source; }
		private boolean hasNextByte() {
			if ( ptr < buflen ) return true;
			else {
				ptr = 0;
				try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); }
				if ( buflen <= 0 ) return false;
			}
			return true;
		} 
		private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; } 
		private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; }
		private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; }
		private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; }
		public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); }
		public String next() {
			if ( !hasNext() ) throw new NoSuchElementException();
			StringBuilder ret = new StringBuilder();
			int b = readByte();
			while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); }
			return ret.toString();
		}
		public long nextLong() {
			if ( !hasNext() ) throw new NoSuchElementException();
			long ret = 0;
			int b = readByte();
			boolean negative = false;
			if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); }
			if ( !isNumeric(b) ) throw new NumberFormatException();
			while ( true ) {
				if ( isNumeric(b) ) ret = ret * 10 + b - '0';
				else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
		public int nextInt() { return (int)nextLong(); }
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}

JavaScript solution:
/// source code (in typescript)

// // @kariay1975/atcoder-tslib is a private package: 
// import {
//   Input,
//   InputStdin,
//   Mod,
//   Output,
//   int,
//   isControlTag,
//   modint,
//   sumNumber,
// } from '@kariya1975/atcoder-tslib';
// // use babel-plugin-macros for speed.
// import {
//   arrayWith,
//   enumerate,
//   range,
// } from '@kariya1975/atcoder-tslib/macro';
// import { ellint_1 } from 'tstl';
// import { swap } from 'typescript-collections/dist/lib/arrays';
// 
// 
// const mod = new Mod(998244353);
// 
// // const naive = (N: int, K: int, S: string): modint => {
// //   let ss = new Set<string>([S]);
// //   for (const _ of range(K)) {
// //     const t = new Set<string>(ss);
// //     for (const s of ss) {
// //       for (const i of range(N)) {
// //         for (const j of range(i + 1, N)) {
// //           const u = s.split('');
// //           swap(u, i, j);
// //           t.add(u.join(''));
// //         }
// //       }
// //     }
// //     ss = t;
// //   }
// //   return mod.fromInt(ss.size);
// // };
// 
// // const solve0 = (N: int, K: int, S: string): modint => {
// //   // return naive(N, K, S);
// 
// //   const A = 0;
// //   const B = 1;
// //   const C = 2;
// //   const fromChar = (c: string): int => c === 'A' ? A : c === 'B' ? B : C;
// //   const s = S.split('').map(c => fromChar(c));
// //   // s, t の同じ位置の文字の文字の対の個数
// //   // assert: sとtは並び替えになっている
// //   const count = (s: int[], t: int[]): int[][] => {
// //     const c = arrayWith(3, () => arrayWith(3, () => 0));
// //     for (const i of range(N)) {
// //       for (const c1 of range(3)) {
// //         for (const c2 of range(3)) {
// //           if (s[i] === c1 && t[i] === c2) c[c1][c2] += 1;
// //         }
// //       }
// //     }
// //     return c;
// //   };
// //   // S -> t となる最小のswap回数
// //   // assert: sとtは並び替えになっている
// //   const f = (s: int[], t: int[]): int => {
// //     const c = count(s, t);
// // // console.error(sumNumber(c.map(x => sumNumber(x))));
// //     let result = 0;
// //     const minAB = Math.min(c[A][B], c[B][A]);
// //     const minBC = Math.min(c[B][C], c[C][B]);
// //     const minCA = Math.min(c[C][A], c[A][C]);
// //     result += minAB;
// //     result += minBC;
// //     result += minCA;
// //     c[A][B] -= minAB;
// //     c[B][A] -= minAB;
// //     c[B][C] -= minBC;
// //     c[C][B] -= minBC;
// //     c[C][A] -= minCA;
// //     c[A][C] -= minCA;
// //     const AB = Math.max(c[A][B], c[B][A]);
// //     const BC = Math.max(c[B][C], c[C][B]);
// //     const CA = Math.max(c[C][A], c[A][C]);
// // if (!(AB === BC && BC === CA)) console.error(AB, BC, CA)
// //     result += (AB + BC + CA) * 2 / 3;
// //     return result;
// //   };
// 
// //   const dfs = (t: int[], k: int): modint => {
// // // console.error(t, f(s, t), k)
// //     if (k === K) {
// //       return mod.fromInt(1);
// //     }
// //     let result = mod.fromInt(1);
// //     for (const i of range(N)) {
// //       for (const j of range(i + 1, N)) {
// //         const u = [...t];
// //         swap(u, i, j);
// //         if (f(s, u) === k + 1) {
// //           result = mod.add(result, dfs(u, k + 1));
// //         }
// //       }
// //     }
// //     return result;
// //   };
// //   return dfs(s, 0);
// // };
// 
// const solve = (N: int, K: int, S: string): modint => {
//   let cA = 0;
//   let cB = 0;
//   let cC = 0;
//   for (const c of S) {
//     if (c === 'A') cA += 1;
//     if (c === 'B') cB += 1;
//     if (c === 'C') cC += 1;
//   }
// 
//   const comb = (n: int, m: int): modint => {
//     return mod.combination(n, m);
//     // let t = mod.fromInt(1);
//     // // let u = mod.fromInt(1);
//     // for (const i of range(m)) {
//     //   t = mod.mult(t, mod.fromInt(n - i));
//     //   // u = mod.mult(u, mod.fromInt(m - i));
//     // }
//     // // return mod.divide(t, u);
//     // const u = mod.factorialInv(m);
//     // return mod.mult(t, u);
//   };
// 
//   let result = mod.fromInt(0);
//   const tt = mod.mult(mod.factorial(cA), mod.mult(mod.factorial(cB), mod.factorial(cC)));
//   for (const i of range(Math.ceil((K + 1) / 2))) {
//     for (const j1 of range(K + 1 - i * 2)) {
//       // let found1 = false;
//       for (const j2 of range(Math.min(cB - i - j1 + 1, K + 1 - i * 2 - j1))) {
//         // let found2 = false;
//         // if (cB < i + j1 + j2) break;
//         // const t2 = mod.mult(comb(cB, i + j2), comb(cB - i - j2, j1));
//         const t2 = mod.mult(mod.mult(mod.factorialInv(i + j2), mod.factorialInv(j1)), mod.factorialInv(cB - i - j2 - j1));
//         for (const j3 of range(Math.min(cA - i - j1 + 1, cC - i - j2 + 1, K + 1 - i * 2 - j1 - j2))) {
//           // if (i * 2 + j1 + j2 + j3 > K) break;
//           // if (cA < i + j1 + j3) break;
//           // if (cB < i + j1 + j2) break;
//           // if (cC < i + j2 + j3) break;
//           // found2 = true;
//           // const t1 = mod.mult(comb(cA, i + j1), comb(cA - i - j1, j3));
//           // const t2 = mod.mult(comb(cB, i + j2), comb(cB - i - j2, j1));
//           // const t3 = mod.mult(comb(cC, i + j3), comb(cC - i - j3, j2));
//           // const t1 = mod.mult(mod.factorial(cA), mod.mult(mod.mult(mod.factorialInv(i + j1), mod.factorialInv(j3)), mod.factorialInv(cA - i - j1 - j3)));
//           // const t2 = mod.mult(mod.factorial(cB), mod.mult(mod.mult(mod.factorialInv(i + j2), mod.factorialInv(j1)), mod.factorialInv(cB - i - j2 - j1)));
//           // const t3 = mod.mult(mod.factorial(cC), mod.mult(mod.mult(mod.factorialInv(i + j3), mod.factorialInv(j2)), mod.factorialInv(cC - i - j3 - j2)));
//           // let t = mod.mult(t1, mod.mult(t2, t3));
//           const t1 = mod.mult(mod.mult(mod.factorialInv(i + j1), mod.factorialInv(j3)), mod.factorialInv(cA - i - j1 - j3));
//           // const t2 = mod.mult(mod.mult(mod.factorialInv(i + j2), mod.factorialInv(j1)), mod.factorialInv(cB - i - j2 - j1));
//           const t3 = mod.mult(mod.mult(mod.factorialInv(i + j3), mod.factorialInv(j2)), mod.factorialInv(cC - i - j3 - j2));
//           let t = mod.mult(tt, mod.mult(t1, mod.mult(t2, t3)));
//           if (i > 0) t = mod.mult(t, mod.fromInt(2)); 
// // console.error(i, j1, j2, j3, t)
//           result = mod.add(result, t);
//         }
//         // if (!found2) break;
//         // found1 = true;
//       }
//       // if (!found1) break;
//     }
//   }
//   return result;
// };
// 
// 
// const main = (input: Input, output: Output): void => {
//   const [N, K] = input.getInts(2);
//   const S = input.getString();
//   const result = solve(N, K, S);
//   output.push(result);
// };
// 
// const input = new InputStdin();
// input.setup().then(_ => {
//   const output = new Output();
//   try {
//     main(input, output);
//     output.print();
//   } catch (e) {
//     if (isControlTag(e, 'earlyExit')) {
//       output.print();
//     }
//   }
// });

// /// The code above transpiles as follows:
var tt=Object.create;var I=Object.defineProperty;var et=Object.getOwnPropertyDescriptor;var rt=Object.getOwnPropertyNames;var it=Object.getPrototypeOf,nt=Object.prototype.hasOwnProperty;var st=(i,t,e)=>t in i?I(i,t,{enumerable:!0,configurable:!0,writable:!0,value:e}):i[t]=e;var ot=i=>I(i,"__esModule",{value:!0});var F=(i,t)=>()=>(t||i((t={exports:{}}).exports,t),t.exports);var ut=(i,t,e)=>{if(t&&typeof t=="object"||typeof t=="function")for(let r of rt(t))!nt.call(i,r)&&r!=="default"&&I(i,r,{get:()=>t[r],enumerable:!(e=et(t,r))||e.enumerable});return i},E=i=>ut(ot(I(i!=null?tt(it(i)):{},"default",i&&i.__esModule&&"default"in i?{get:()=>i.default,enumerable:!0}:{value:i,enumerable:!0})),i);var M=(i,t,e)=>(st(i,typeof t!="symbol"?t+"":t,e),e);var O=F((Ft,L)=>{"use strict";var at=function(i,t){return i<t};function c(i){if(!(this instanceof c))return new c(i);this.array=[],this.size=0,this.compare=i||at}c.prototype.clone=function(){var i=new c(this.compare);return i.size=this.size,i.array=this.array.slice(0,this.size),i};c.prototype.add=function(i){var t=this.size;this.array[this.size]=i,this.size+=1;for(var e,r;t>0&&(e=t-1>>1,r=this.array[e],!!this.compare(i,r));)this.array[t]=r,t=e;this.array[t]=i};c.prototype.heapify=function(i){this.array=i,this.size=i.length;var t;for(t=this.size>>1;t>=0;t--)this._percolateDown(t)};c.prototype._percolateUp=function(i,t){for(var e=this.array[i],r,n;i>0&&(r=i-1>>1,n=this.array[r],!(!t&&!this.compare(e,n)));)this.array[i]=n,i=r;this.array[i]=e};c.prototype._percolateDown=function(i){for(var t=this.size,e=this.size>>>1,r=this.array[i],n,s,o;i<e&&(n=(i<<1)+1,s=n+1,o=this.array[n],s<t&&this.compare(this.array[s],o)&&(n=s,o=this.array[s]),!!this.compare(o,r));)this.array[i]=o,i=n;this.array[i]=r};c.prototype._removeAt=function(i){if(!(i>this.size-1||i<0))return this._percolateUp(i,!0),this.poll()};c.prototype.remove=function(i){for(var t=0;t<this.size;t++)if(!this.compare(this.array[t],i)&&!this.compare(i,this.array[t]))return this._removeAt(t),!0;return!1};c.prototype.removeOne=function(i){if(typeof i=="function"){for(var t=0;t<this.size;t++)if(i(this.array[t]))return this._removeAt(t)}};c.prototype.removeMany=function(i,t){if(typeof i!="function"||this.size<1)return[];t=t?Math.min(t,this.size):this.size;for(var e=0,r=new Array(t),n=0,s=new Array(this.size);e<t&&!this.isEmpty();){var o=this.poll();i(o)?r[e++]=o:s[n++]=o}r.length=e;for(var a=0;a<n;)this.add(s[a++]);return r};c.prototype.peek=function(){if(this.size!=0)return this.array[0]};c.prototype.poll=function(){if(this.size!=0){var i=this.array[0];return this.size>1?(this.array[0]=this.array[--this.size],this._percolateDown(0)):this.size-=1,i}};c.prototype.replaceTop=function(i){if(this.size!=0){var t=this.array[0];return this.array[0]=i,this._percolateDown(0),t}};c.prototype.trim=function(){this.array=this.array.slice(0,this.size)};c.prototype.isEmpty=function(){return this.size===0};c.prototype.forEach=function(i){if(!(this.isEmpty()||typeof i!="function"))for(var t=0,e=this.clone();!e.isEmpty();)i(e.poll(),t++)};c.prototype.kSmallest=function(i){if(this.size==0)return[];i=Math.min(this.size,i);var t=new c(this.compare);let e=Math.min((i>0?Math.pow(2,i-1):0)+1,this.size);t.size=e,t.array=this.array.slice(0,e);for(var r=new Array(i),n=0;n<i;n++)r[n]=t.poll();return r};L.exports=c});var P=F((Yt,C)=>{"use strict";function u(i){if(this._capacity=$(i),this._length=0,this._front=0,B(i)){for(var t=i.length,e=0;e<t;++e)this[e]=i[e];this._length=t}}u.prototype.toArray=function(){for(var t=this._length,e=new Array(t),r=this._front,n=this._capacity,s=0;s<t;++s)e[s]=this[r+s&n-1];return e};u.prototype.push=function(t){var e=arguments.length,r=this._length;if(e>1){var n=this._capacity;if(r+e>n){for(var o=0;o<e;++o){this._checkCapacity(r+1);var s=this._front+r&this._capacity-1;this[s]=arguments[o],r++,this._length=r}return r}else{for(var s=this._front,o=0;o<e;++o)this[s+r&n-1]=arguments[o],s++;return this._length=r+e,r+e}}if(e===0)return r;this._checkCapacity(r+1);var o=this._front+r&this._capacity-1;return this[o]=t,this._length=r+1,r+1};u.prototype.pop=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1,r=this[e];return this[e]=void 0,this._length=t-1,r}};u.prototype.shift=function(){var t=this._length;if(t!==0){var e=this._front,r=this[e];return this[e]=void 0,this._front=e+1&this._capacity-1,this._length=t-1,r}};u.prototype.unshift=function(t){var e=this._length,r=arguments.length;if(r>1){var o=this._capacity;if(e+r>o){for(var a=r-1;a>=0;a--){this._checkCapacity(e+1);var o=this._capacity,n=(this._front-1&o-1^o)-o;this[n]=arguments[a],e++,this._length=e,this._front=n}return e}else{for(var s=this._front,a=r-1;a>=0;a--){var n=(s-1&o-1^o)-o;this[n]=arguments[a],s=n}return this._front=s,this._length=e+r,e+r}}if(r===0)return e;this._checkCapacity(e+1);var o=this._capacity,a=(this._front-1&o-1^o)-o;return this[a]=t,this._length=e+1,this._front=a,e+1};u.prototype.peekBack=function(){var t=this._length;if(t!==0){var e=this._front+t-1&this._capacity-1;return this[e]}};u.prototype.peekFront=function(){if(this._length!==0)return this[this._front]};u.prototype.get=function(t){var e=t;if(e===(e|0)){var r=this._length;if(e<0&&(e=e+r),!(e<0||e>=r))return this[this._front+e&this._capacity-1]}};u.prototype.isEmpty=function(){return this._length===0};u.prototype.clear=function(){for(var t=this._length,e=this._front,r=this._capacity,n=0;n<t;++n)this[e+n&r-1]=void 0;this._length=0,this._front=0};u.prototype.toString=function(){return this.toArray().toString()};u.prototype.valueOf=u.prototype.toString;u.prototype.removeFront=u.prototype.shift;u.prototype.removeBack=u.prototype.pop;u.prototype.insertFront=u.prototype.unshift;u.prototype.insertBack=u.prototype.push;u.prototype.enqueue=u.prototype.push;u.prototype.dequeue=u.prototype.shift;u.prototype.toJSON=u.prototype.toArray;Object.defineProperty(u.prototype,"length",{get:function(){return this._length},set:function(){throw new RangeError("")}});u.prototype._checkCapacity=function(t){this._capacity<t&&this._resizeTo($(this._capacity*1.5+16))};u.prototype._resizeTo=function(t){var e=this._capacity;this._capacity=t;var r=this._front,n=this._length;if(r+n>e){var s=r+n&e-1;dt(this,0,this,e,s)}};var B=Array.isArray;function dt(i,t,e,r,n){for(var s=0;s<n;++s)e[s+r]=i[s+t],i[s+t]=void 0}function mt(i){return i=i>>>0,i=i-1,i=i|i>>1,i=i|i>>2,i=i|i>>4,i=i|i>>8,i=i|i>>16,i+1}function $(i){if(typeof i!="number")if(B(i))i=i.length;else return 16;return mt(Math.min(Math.max(16,i),1073741824))}C.exports=u});var v=E(require("fs")),D=class{constructor(t){this.data=t!=null?t:"",this.index=0}isSpace(t){return t===" "||t===`
`}getString(){for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;let t=this.index;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)this.index++;let e=this.index;return this.data.slice(t,e)}getCharList(){let t=[];for(;this.index<this.data.length&&this.isSpace(this.data[this.index]);)this.index++;for(;this.index<this.data.length&&!this.isSpace(this.data[this.index]);)t.push(this.data[this.index]),this.index++;return t}getBigInt(){return BigInt(this.getString())}getInt(){return Number(this.getString())}getNumber(){return Number(this.getString())}getNumbers(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getNumber());return e}getBigInts(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getBigInt());return e}getInts(t){let e=Array(t);for(let r=0,n=t;r<n;++r)e[r]=this.getInt();return e}getStrings(t){let e=[];for(let r=0,n=t;r<n;++r)e.push(this.getString());return e}getMatrix(){let[t,e]=this.getInts(2),r=[];for(let n=0,s=t;n<s;++n)r.push(this.getInts(e));return[t,e,r]}getMatrixWithExtraData(t){let[e,r]=this.getInts(2),n=this.getInts(t),s=[];for(let o=0,a=e;o<a;++o)s.push(this.getInts(r));return[e,r,n,s]}getSquareMatrix(){let t=this.getInt(),e=[];for(let r=0,n=t;r<n;++r)e.push(this.getInts(t));return[t,e]}forEach(t){let e=this.getInt();for(let r=0,n=e;r<n;++r)t(r)}case(t){let e=this.getInt();if(!t.has(e))throw new Error(`unknown kind ${e}`);t.get(e)(e)}getSeries(){let t=this.getInt(),e=this.getInts(t);return[t,e]}getSeriesWithExtraData(t){let e=this.getInt(),r=this.getInts(t),n=this.getInts(e);return[[e,...r],n]}getGraphWithAdjList(){let[t,e]=this.getInts(2),r=f(t,()=>[]);for(let n=0,s=e;n<s;++n){let[o,a]=this.getInts(2);r[o-1].push(a-1),r[a-1].push(o-1)}return[t,e,r]}getGraphWithAdjMatrix(){let[t,e]=this.getInts(2),r=f(t,()=>f(t,()=>!1));for(let n=0,s=e;n<s;++n){let[o,a]=this.getInts(2);r[o-1][a-1]=!0,r[a-1][o-1]=!0}return[t,e,r]}},S=class extends D{constructor(){super();(0,v.existsSync)("/dev/stdin")&&(super.data=(0,v.readFileSync)("/dev/stdin","utf-8"))}async setup(){if((0,v.existsSync)("/dev/stdin"))return;let t=[];for await(let n of process.stdin)t.push(n);let r=Buffer.concat(t).toString();super.data=r}};var ht=E(O());var gt=E(P());var f=(i,t)=>{let e=new Array(i);for(let r=0;r<i;++r)e[r]=t(r);return e};var Q=G((i,t)=>t===0?i:()=>Q(t,i%t));var T=G((i,t)=>t===0n?i:()=>T(t,i%t));function G(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var xt=H((i,t)=>{if(t.length===0)return i;let[e,...r]=t;return()=>xt(i[e],r)}),vt=H((i,t,e)=>{let[r,...n]=t;if(n.length>0)return()=>vt(i[r],n,e);i[r]=e});function H(i){return function(...e){let r=i(...e);for(;typeof r=="function";)r=r();return r}}var q=class{constructor(t){this.mod=t,this.mod=t,this.invTable=new Map,this.invTable.set(0,0),this.invTable.set(1,1),this.factorialTable=[1],this.factorialInvTable=[1]}fromInt(t){return t}inv_slow(t){let e=1;for(let r=0,n=this.mod-2;r<n;++r)e=this.mult(e,t);return e}_mult(t,e){let r=t*e;return r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number(BigInt(t)*BigInt(e)%BigInt(this.mod))}mult(t,e){let r=t*e;return r<=Number.MAX_SAFE_INTEGER?r%this.mod:(t%4096*e+Math.floor(t/4096)*e%this.mod*4096)%this.mod}inv_slow2(t){let e=this.mod-2,r=t,n=1;for(;e>0;)(e&1)==1&&(n=this.mult(n,r)),r=this.mult(r,r),e=e>>1;return n}inv(t){if(this.invTable.has(t))return this.invTable.get(t);let e=t,r=this.mod-this.mult(Math.floor(this.mod/e),this.inv(this.mod%e));return this.invTable.set(t,r),r}factorial(t){if(this.factorialTable.length<=t)for(let e=this.factorialTable.length;e<t+1;++e)this.factorialTable.push(this.mult(this.factorialTable[e-1],e));return this.factorialTable[t]}factorial_fast(t,e=[0]){if(e[0]=0,t===0)return 1;let r=Math.floor(t/this.mod),n=this.factorial_fast(r,e);return e[0]+=r,r%2!=0?this.mult(n,this.mod-this.factorial(t%this.mod)):this.mult(n,this.factorial(t%this.mod))}factorialInv(t){if(this.factorialInvTable.length<=t)for(let e=this.factorialInvTable.length;e<t+1;++e)this.factorialInvTable.push(this.mult(this.factorialInvTable[e-1],this.inv(e)));return this.factorialInvTable[t]}combination(t,e){let r=this.factorial(t);return r=this.mult(r,this.mult(this.factorialInv(t-e),this.factorialInv(e))),r}add(t,e){let r=t+e;return r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number((BigInt(t)+BigInt(e))%BigInt(this.mod))}sub(t,e){let r=t-e;return r<0&&(r+=this.mod),r<=Number.MAX_SAFE_INTEGER?r%this.mod:Number((BigInt(t)-BigInt(e))%BigInt(this.mod))}divide(t,e){return this.mult(t,this.inv_slow2(e))}normalize(t){return t>=0&&t<this.mod?t:t>=0?t%this.mod:t%this.mod+this.mod}mults(t){if(t.length===0)return 1;let[e,...r]=t;return this.mult(e,this.mults(r))}pow(t,e){if(e===0)return 1;if(e%2==0){let n=this.pow(t,e/2);return this.mult(n,n)}let r=this.pow(t,Math.floor(e/2));return this.mult(this.mult(r,r),t)}};var b=(i,t,e,r)=>{let n=t.length;if(n===1)return t;let s=[],o=[];for(let d=0,m=n;d<m;++d)d%2==0?s.push(t[d]):o.push(t[d]);let a=b(i,s,e-1,r),g=b(i,o,e-1,r),h=r[e],y=1,p=[];for(let d=0,m=n;d<m;++d)p.push(i.add(a[d%(n/2)],i.mult(y,g[d%(n/2)]))),y=i.mult(y,h);return p},It=(i,t,e,r,n)=>{let s=t.length,o=e.length,a=s+o-1,g=1,h=0;for(;g<=a;)g*=2,h+=1;for(;t.length<g;)t.push(0);for(;e.length<g;)e.push(0);let y=b(i,t,h-1,r),p=b(i,e,h-1,r),d=f(g,_=>i.mult(y[_],p[_]));return b(i,d,h-1,n).map(_=>i.divide(_,g))},St=i=>{let t=[],e=i.pow(3,119);for(let r=0,n=23;r<n;++r)t.push(e),e=i.mult(e,e);return t.reverse(),t},qt=(i,t)=>t.map(e=>i.inv(e)),w=class{constructor(t){this.mod=t,w.root.length===0&&(w.root=St(t),w.invroot=qt(t,w.root))}convolution(t,e){return It(this.mod,t,e,w.root,w.invroot)}},z=w;M(z,"root",[]),M(z,"invroot",[]);var N=class{buffer=[];constructor(){}push(t){this.buffer.push(t)}yesNo(t){this.push(t?"Yes":"No")}list(t){this.push(t.join(" "))}lists(t){this.push(t.length);for(let e of t)this.list(e)}print(){console.log(this.buffer.join(`
`))}earlyExitTag(){return"earlyExit"}isEarlyExitTag(t){return t==="earlyExit"}};var X=(i,t)=>i===t;var k=X;var l=new q(998244353),Et=(i,t,e)=>{let r=0,n=0,s=0;for(let h of e)h==="A"&&(r+=1),h==="B"&&(n+=1),h==="C"&&(s+=1);let o=(h,y)=>l.combination(h,y),a=l.fromInt(0),g=l.mult(l.factorial(r),l.mult(l.factorial(n),l.factorial(s)));for(let h=0,y=Math.ceil((t+1)/2);h<y;++h)for(let p=0,d=t+1-h*2;p<d;++p)for(let m=0,_=Math.min(n-h-p+1,t+1-h*2-p);m<_;++m){let J=l.mult(l.mult(l.factorialInv(h+m),l.factorialInv(p)),l.factorialInv(n-h-m-p));for(let x=0,V=Math.min(r-h-p+1,s-h-m+1,t+1-h*2-p-m);x<V;++x){let Z=l.mult(l.mult(l.factorialInv(h+p),l.factorialInv(x)),l.factorialInv(r-h-p-x)),K=l.mult(l.mult(l.factorialInv(h+x),l.factorialInv(m)),l.factorialInv(s-h-x-m)),A=l.mult(g,l.mult(Z,l.mult(J,K)));h>0&&(A=l.mult(A,l.fromInt(2))),a=l.add(a,A)}}return a},Mt=(i,t)=>{let[e,r]=i.getInts(2),n=i.getString(),s=Et(e,r,n);t.push(s)},Y=new S;Y.setup().then(i=>{let t=new N;try{Mt(Y,t),t.print()}catch(e){k(e,"earlyExit")&&t.print()}});

Python solution:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 998244353

    N, K = map(int, input().split())
    Ss = input().rstrip()

    numA = numB = numC = 0
    for S in Ss:
        if S == 'A':
            numA += 1
        elif S == 'B':
            numB += 1
        else:
            numC += 1
    #print('# numA:', numA, '/ numB:', numB, '/ numC:', numC)

    def getFacts(n, MOD):
        facts = [1] * (n+1)
        for x in range(2, n+1):
            facts[x] = (facts[x-1] * x) % MOD
        return facts
    facts = getFacts(N+K+5, MOD)
    def getInvFacts(n, MOD):
        invFacts = [0] * (n+1)
        invFacts[n] = pow(facts[n], MOD-2, MOD)
        for x in reversed(range(n)):
            invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
        return invFacts
    invFacts = getInvFacts(N+K+5, MOD)

    fA = facts[numA]
    fB = facts[numB]
    fC = facts[numC]
    fA_B_C = fA * fB % MOD * fC % MOD

    ans = 0
    for AB in range(K+1):
        ifAB = invFacts[AB]
        for BC in range(K-AB+1):
            if AB+BC > numB:
                break
            ifBC = invFacts[BC]
            ifAB_BC = ifAB * ifBC % MOD
            for CA in range(K-AB-BC+1):
                if AB+CA > numA:
                    break
                if BC+CA > numC:
                    break
                ifCA = invFacts[CA]
                ifAB_BC_CA = ifAB_BC * ifCA % MOD
                v = fA_B_C * ifAB_BC_CA % MOD
                for ABC in range((K-AB-BC-CA)//2+1):
                    A = AB+CA+ABC
                    if A > numA:
                        break
                    B = AB+BC+ABC
                    if B > numB:
                        break
                    C = BC+CA+ABC
                    if C > numC:
                        break
    #                print('\n##### AB:', AB, '/ BC:', BC, '/ CA:', CA, '/ ABC:', ABC)
                    # A->B->C
                    num = v
                    num *= invFacts[AB+ABC] * invFacts[BC+ABC] % MOD * invFacts[CA+ABC] % MOD
                    num %= MOD
                    num *= invFacts[numA-AB-CA-ABC] * invFacts[numB-AB-BC-ABC] % MOD * invFacts[numC-BC-CA-ABC] % MOD
                    num %= MOD
                    ans += num
                    if ABC > 0:
                        # A<-B<-C
                        ans += num
                    ans %= MOD

    print(ans)


solve()

Ruby solution:
require 'set'

MOD = 998244353

def solve
  input = $stdin.read.split
  idx = 0
  n = input[idx].to_i
  idx += 1
  k = input[idx].to_i
  idx += 1
  s = input[idx]
  idx += 1

  count_a = s.count('A')
  count_b = s.count('B')
  count_c = s.count('C')

  max_fact = [n + k + 5, count_a + count_b + count_c + k + 5].max
  fact = Array.new(max_fact + 1, 1)
  (2..max_fact).each do |i|
    fact[i] = (fact[i-1] * i) % MOD
  end

  inv_fact = Array.new(max_fact + 1, 1)
  inv_fact[max_fact] = fact[max_fact].pow(MOD - 2, MOD)
  (max_fact - 1).downto(0) do |i|
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD
  end

  f_a = fact[count_a]
  f_b = fact[count_b]
  f_c = fact[count_c]
  f_a_b_c = (f_a * f_b) % MOD * f_c % MOD

  ans = 0

  (0..[k, count_b].min).each do |ab|
    if_ab = inv_fact[ab]
    (0..[k - ab, count_b - ab].min).each do |bc|
      if_bc = inv_fact[bc]
      if_ab_bc = (if_ab * if_bc) % MOD
      (0..[k - ab - bc, count_a - ab, count_c - bc].min).each do |ca|
        if_ca = inv_fact[ca]
        if_ab_bc_ca = (if_ab_bc * if_ca) % MOD
        v = (f_a_b_c * if_ab_bc_ca) % MOD
        max_abc = [(k - ab - bc - ca) / 2, 
                  count_a - ab - ca,
                  count_b - ab - bc,
                  count_c - bc - ca].min
        (0..max_abc).each do |abc|
          a = ab + ca + abc
          b = ab + bc + abc
          c = bc + ca + abc
          next if a > count_a || b > count_b || c > count_c

          num = v
          num = num * inv_fact[ab + abc] % MOD
          num = num * inv_fact[bc + abc] % MOD
          num = num * inv_fact[ca + abc] % MOD
          num = num * inv_fact[count_a - a] % MOD
          num = num * inv_fact[count_b - b] % MOD
          num = num * inv_fact[count_c - c] % MOD
          ans = (ans + num) % MOD
          if abc > 0
            ans = (ans + num) % MOD
          end
        end
      end
    end
  end

  puts ans
end

solve