package main import ( "bufio" "fmt" "math" "math/big" "os" "strconv" ) // 解答欄 func solve(sc *myScanner, wr *myWriter) { p := newModulus(998244353) n, m, k := sc.getInt3() as := func() []int { rs := sc.getRunes() res := make([]int, len(rs)) for i, r := range rs { res[i] = int(r - 'a') } return res }() set := make(map[int]bool) dp := make([][]int, m+1) for i := range dp { dp[i] = make([]int, 27) } dp[0][0] = 1 for i := 0; i < m; i++ { for j := 0; j <= 26; j++ { x := dp[i][j] if i < n && len(set) == j { a := as[i] cntExist := 0 for b := 0; b < a; b++ { if set[b] { cntExist++ } } dp[i+1][j] = p.add(dp[i+1][j], cntExist) if j+1 <= 26 { dp[i+1][j+1] = p.add(dp[i+1][j+1], a-cntExist) } if set[a] { dp[i+1][j] = p.add(dp[i+1][j], 1) } else { dp[i+1][j+1] = p.add(dp[i+1][j+1], 1) } x = p.sub(x, 1) } else if i == n && len(set) == j { x = p.sub(x, 1) } dp[i+1][j] = p.add(dp[i+1][j], x*j) if j+1 <= 26 { dp[i+1][j+1] = p.add(dp[i+1][j+1], x*(26-j)) } } if i < n { set[as[i]] = true } } ans := 0 for i := 1; i <= m; i++ { for j := k; j <= 26; j++ { ans = p.add(ans, dp[i][j]) } } if len(set) >= k { ans = p.sub(ans, 1) } wr.println(ans) } // modulo tools type modulus int const defaultModP = int(1e9) + 7 func newModulus(p int) *modulus { m := modulus(p) return &m } func (m *modulus) mod(a int) int { if a < 0 || a >= int(*m) { a %= int(*m) } if a < 0 { a += int(*m) } return a } func (m *modulus) add(a, b int) int { return m.mod(a + b) } func (m *modulus) sub(a, b int) int { return m.mod(a - b) } func (m *modulus) mul(a, b int) int { return m.mod(a * b) } func (m *modulus) div(a, b int) int { return m.mul(a, m.inv(b)) } func (m *modulus) inv(a int) int { x, _ := extGcd(a, int(*m)) return x } func (m *modulus) pow(a, n int) int { res := 1 b := m.mod(a) for n > 0 { if n&1 > 0 { res = m.mul(res, b) } n >>= 1 b = m.mul(b, b) } return res } func extGcd(a, b int) (int, int) { x0, y0 := 1, 0 x1, y1 := 0, 1 for a%b != 0 { q := a / b r := a % b x2, y2 := x0-q*x1, y0-q*y1 a, b = b, r x0, y0 = x1, y1 x1, y1 = x2, y2 } return x1, y1 } // 入出力の準備(sc, wr) func main() { sc := &myScanner{bufio.NewScanner(os.Stdin)} wr := &myWriter{bufio.NewWriter(os.Stdout)} startBufSize := 4096 maxBufSize := math.MaxInt64 sc.Buffer(make([]byte, startBufSize), maxBufSize) sc.Split(bufio.ScanWords) solve(sc, wr) wr.Flush() } // useful funcs for slice func makeInts(n, x int) []int { res := make([]int, n) for i := range res { res[i] = x } return res } func makeBools(n int, b bool) []bool { res := make([]bool, n) for i := range res { res[i] = b } return res } func countTrue(bs []bool) int { res := 0 for _, b := range bs { if b { res++ } } return res } // input type myScanner struct { *bufio.Scanner } func (sc *myScanner) getInt() int { return sc._getIntOffset(0) } func (sc *myScanner) getInt2() (int, int) { return sc.getInt(), sc.getInt() } func (sc *myScanner) getInt3() (int, int, int) { return sc.getInt(), sc.getInt(), sc.getInt() } func (sc *myScanner) getInt4() (int, int, int, int) { return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt() } func (sc *myScanner) getInts(n int) []int { return sc._getIntsOffset(n, 0) } func (sc *myScanner) getIntZeroIndexed() int { return sc._getIntOffset(-1) } func (sc *myScanner) getIntsZeroIndexed(n int) []int { return sc._getIntsOffset(n, -1) } func (sc *myScanner) _getIntOffset(x int) int { res, err := strconv.Atoi(sc.getString()) if err != nil { panic(err) } return res + x } func (sc *myScanner) _getIntsOffset(n, x int) []int { res := make([]int, n) for i := range res { res[i] = sc._getIntOffset(x) } return res } func (sc *myScanner) getString() string { sc.Scan() return sc.Text() } func (sc *myScanner) getStrings(n int) []string { res := make([]string, n) for i := range res { res[i] = sc.getString() } return res } func (sc *myScanner) getRunes() []rune { return []rune(sc.getString()) } func (sc *myScanner) getFloat() float64 { res, err := strconv.ParseFloat(sc.getString(), 64) if err != nil { panic(err) } return res } func (sc *myScanner) getFloats(n int) []float64 { res := make([]float64, n) for i := range res { res[i] = sc.getFloat() } return res } // output type myWriter struct { *bufio.Writer } func (wr *myWriter) println(a ...interface{}) { fmt.Fprintln(wr, a...) } func (wr *myWriter) printf(format string, a ...interface{}) { fmt.Fprintf(wr, format, a...) } // simple math funcs for int func max(as ...int) int { res := as[0] for _, a := range as { if res < a { res = a } } return res } func min(as ...int) int { res := as[0] for _, a := range as { if res > a { res = a } } return res } func chMax(a *int, b int) { *a = max(*a, b) } func chMin(a *int, b int) { *a = min(*a, b) } func abs(a int) int { if a < 0 { return -a } return a } func pow(a, n int) int { res := 1 b := a for n > 0 { if n&1 > 0 { res *= b } n >>= 1 b *= b } return res } func sum(s ...int) int { res := 0 for _, v := range s { res += v } return res } func checkPrime(a int) bool { if a == 2 { return true } else if a%2 == 0 { return false } res := true for q := 3; q*q <= a; q += 2 { if a%q == 0 { res = false break } } return res } func toBInt(a int) *big.Int { return big.NewInt(int64(a)) } /* めも int(64)の最大値: 9223372036854775807 = (2^63 - 1) 19桁 10^18 < 2^60 < 2^63 < 10^19 10^19 はintだとオーバーフローする sliceの長さ: 10^8程度までは許される 型によるがそれ以上は Out of memory の危険がある 1~nの和: {n*(n+1)}/2 (1~nの平均値)*n を式変形したもの 先に掛け算をすることで必ず2で割り切れる */