Inverse Problem
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 2700
Tags: *special, combinatorics, dp

Consider the following problem.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters, and an integer $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$). Each letter is one of the first $$$c$$$ letters of the alphabet.

You apply the following operation until the length of the string is less than $$$k$$$: choose a contiguous substring of the string of length exactly $$$k$$$, remove it from the string and glue the resulting parts together without changing the order.

Let the resulting string of length smaller than $$$k$$$ be $$$t$$$. What is lexicographically smallest string $$$t$$$ that can obtained?

You are asked the inverse of this problem. Given two integers $$$n$$$ and $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$) and a string $$$t$$$, consisting of ($$$n \bmod k$$$) lowercase Latin letters, count the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

Print that number modulo $$$998\,244\,353$$$.

Input format:
The first line contains three integers $$$n, k$$$ and $$$c$$$ ($$$1 \le n \le 10^6$$$; $$$2 \le k \le 10^6$$$; $$$1 \le c \le 26$$$; $$$n$$$ is not divisible by $$$k$$$) — the length of string $$$s$$$, the length of the substring that is being removed and the number of first letters from the alphabet.

The second line contains string $$$t$$$, consisting of exactly ($$$n \bmod k$$$) lowercase Latin letters. Each letter is one of the first $$$c$$$ letters of the alphabet.

Output format:
Print a single integer — the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The strings $$$s$$$ in the first example: "aaa", "aab", "aba", "abb", "baa", "bba".

The strings $$$s$$$ in the second example: "bcabc", "bcacc", "bcbbc", "bcbcc", "bccbc", "bcccc", "caabc", "cabbc", "cacbc", "cbabc", "cbbbc", "cbcbc", "ccabc", "ccbbc", "cccbc".

Example input:
3 2 2
a

Example output:
6

Example input:
5 3 3
bc

Example output:
15

Editorial:
Let's start by solving the first problem in the statement.
Imagine you removed one substring of length $$$k$$$ from the string. Then you removed another one. There are two outcomes. Either it's two substrings of length $$$k$$$ missing from the original string. Or it's one substring of length $$$2k$$$. Continue the process. At the end, several segments of lengths divisible by $$$k$$$ will be removed from the string.
Consider the first letter of the resulting string $$$t$$$. It comes from the position immediately after the first removed segment (possibly, an empty one). So modulo $$$k$$$ its index is always $$$0$$$. Then the second letter. Again, another segment (possibly, an empty one) separates it from the first letter. So modulo $$$k$$$ its index is always $$$1$$$. So on, until letter $$$n \bmod k$$$ (which is $$$n \bmod k - 1$$$ modulo $$$k$$$) — the last letter.
Each value modulo $$$k$$$ until $$$n \bmod k - 1$$$ will appear exactly once, since $$$n \bmod k$$$ is the length of the resulting string $$$t$$$.
So the following greedy algorithm comes up. Take the smallest letter on position $$$0$$$ modulo $$$k$$$. Among the equal smallest ones, take the leftmost one. Then take the smallest letter on position $$$1$$$ modulo $$$k$$$, which is to the right of the first taken letter. Again, leftmost among the equal ones. Continue until the string $$$t$$$ has length $$$n \bmod k$$$.
Notice that the process will always finish. That's easy to see if you observe how positions that are below $$$(n \bmod k)$$$ modulo $$$k$$$ are placed in the string. The last position in $$$s$$$ is $$$n \bmod k - 1$$$, the second to last is $$$n \bmod k - 2$$$ and so on.
Let's derive the solution to the inverse problem.
Let's build a dynamic programming on the steps of the algorithm. Let $$$dp[i][j]$$$ be the number of strings $$$s$$$ such that the first $$$i$$$ letters in $$$t$$$ are chosen already and $$$j$$$ is the position of the last taken letter in $$$s$$$.
$$$j$$$ is always equal to $$$i - 1 \bmod k$$$, so we can compress the dp. Let $$$j$$$ instead be not the position in $$$s$$$ itself, but a value that says $$$j \cdot k + (i - 1)$$$ is the position in $$$s$$$.
On the compressed dp, the transitions are pretty easy to show. From $$$dp[i][j]$$$ we can go to $$$dp[i + 1][j']$$$ for any $$$j' \ge j$$$. Consider some $$$j'$$$. Since we picked it in the algorithm, all letters between $$$j$$$ and $$$(j' - 1)$$$ are strictly greater than the letter $$$j'$$$. All letter after $$$j'$$$ are greater or equal to $$$j'$$$. All letters before $$$j$$$ can be anything, since we don't consider them in the algorithm. We know the letter that gets picked on each layer — this is $$$t_i$$$. Thus, the value that gets added to $$$dp[i + 1][j']$$$ is $$$dp[i][j]$$$ multiplied by all ways to choose the surrounding letters.
You can't calculate this dp as is, since it's too slow to try all pairs of position in the current layer and the next one. However, this can be sped up with prefix sums.
There are $$$n \bmod k$$$ layers and $$$\lfloor \frac{n}{k} \rfloor + 1$$$ states on each layer.
Don't forget that the positions that are greater or equal to $$$(n \bmod k)$$$ modulo $$$k$$$ won't be included in the answer. So any of $$$c$$$ letters can be placed there. Thus, multiply the values on the last layer of the dp by $$$c$$$ to the power of the number of these positions and sum them up.
Overall complexity: $$$O(n + k)$$$.