← Home
```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD = 998244353

func power(base, exp int64) int64 {
	res := int64(1)
	base %= MOD
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % MOD
		}
		base = (base * base) % MOD
		exp /= 2
	}
	return res
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, k, c int
	fmt.Fscan(reader, &n, &k, &c)
	var t string
	fmt.Fscan(reader, &t)

	m := n % k
	L := n / k

	c_pow := make([]int64, L+1)
	c_pow[0] = 1
	for r := 1; r <= L; r++ {
		c_pow[r] = (c_pow[r-1] * int64(c)) % MOD
	}

	dp := make([]int64, L+1)
	new_dp := make([]int64, L+1)

	A_pow_arr := make([]int64, L+1)
	B_pow_arr := make([]int64, L+1)

	A0 := int64(c - 1 - int(t[0]-'a'))
	B0 := A0 + 1

	A_pow_arr[0] = 1
	for r := 1; r <= L; r++ {
		A_pow_arr[r] = (A_pow_arr[r-1] * A0) % MOD
	}
	B_pow_arr[0] = 1
	for r := 1; r <= L; r++ {
		B_pow_arr[r] = (B_pow_arr[r-1] * B0) % MOD
	}

	for r := 0; r <= L; r++ {
		dp[r] = (A_pow_arr[r] * B_pow_arr[L-r]) % MOD
	}

	for j := 1; j < m; j++ {
		Aj := int64(c - 1 - int(t[j]-'a'))
		Bj := Aj + 1

		B_pow_arr[0] = 1
		for r := 1; r <= L; r++ {
			B_pow_arr[r] = (B_pow_arr[r-1] * Bj) % MOD
		}

		S := int64(0)
		for r := 0; r <= L; r++ {
			term := (dp[r] * c_pow[r]) % MOD
			S = (S*Aj + term) % MOD
			new_dp[r] = (S * B_pow_arr[L-r]) % MOD
		}
		for r := 0; r <= L; r++ {
			dp[r] = new_dp[r]
		}
	}

	ans := int64(0)
	for r := 0; r <= L; r++ {
		ans = (ans + dp[r]) % MOD
	}

	rem_pow := power(int64(c), int64(L)*int64(k-m))
	ans = (ans * rem_pow) % MOD

	fmt.Println(ans)
}
```