310930: CF1910I. Inverse Problem
Description
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$.
InputThe 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.
OutputPrint a single integer — the number of strings $s$ that produce $t$ as the lexicographically smallest solution.
ExamplesInput3 2 2 aOutput
6Input
5 3 3 bcOutput
15Input
34 12 26 codeforcesOutput
988024123Input
5 3 1 aaOutput
1Note
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".
Output
这是一个关于字符串的问题。给定一个由n个小写拉丁字母组成的字符串s和一个整数k（n不能被k整除），每次从字符串中选择一个长度恰好为k的连续子串并将其删除，然后将剩余的部分粘合在一起，直到字符串长度小于k。求最终长度小于k的字符串t的字典序最小值。题目要求的是这个问题的逆问题，即给定n、k和一个由(n mod k)个小写拉丁字母组成的字符串t，计算可以生成字典序最小的t的字符串s的数量。输出这个数量模998,244,353的值。
输入输出数据格式：
输入：
- 第一行包含三个整数n、k和c（1≤n≤10^6；2≤k≤10^6；1≤c≤26；n不能被k整除）——字符串s的长度、被删除子串的长度和字母表前c个字母的数量。
- 第二行包含一个由(n mod k)个小写拉丁字母组成的字符串t，每个字母都是字母表前c个字母之一。
输出：
- 输出一个整数——生成字典序最小的t的字符串s的数量模998,244,353的值。
示例：
输入：
```
3 2 2
a
```
输出：
```
6
```
输入：
```
5 3 3
bc
```
输出：
```
15
```
输入：
```
34 12 26
codeforces
```
输出：
```
988024123
```
输入：
```
5 3 1
aa
```
输出：
```
1
```
注意：
在第一个示例中，生成字符串t="a"的字符串s有："aaa"、"aab"、"aba"、"abb"、"baa"、"bba"。
在第二个示例中，生成字符串t="bc"的字符串s有："bcabc"、"bcacc"、"bcbbc"、"bcbcc"、"bccbc"、"bcccc"、"caabc"、"cabbc"、"cacbc"、"cbabc"、"cbbbc"、"cbcbc"、"ccabc"、"ccbbc"、"cccbc"。题目大意： 这是一个关于字符串的问题。给定一个由n个小写拉丁字母组成的字符串s和一个整数k（n不能被k整除），每次从字符串中选择一个长度恰好为k的连续子串并将其删除，然后将剩余的部分粘合在一起，直到字符串长度小于k。求最终长度小于k的字符串t的字典序最小值。题目要求的是这个问题的逆问题，即给定n、k和一个由(n mod k)个小写拉丁字母组成的字符串t，计算可以生成字典序最小的t的字符串s的数量。输出这个数量模998,244,353的值。 输入输出数据格式： 输入： - 第一行包含三个整数n、k和c（1≤n≤10^6；2≤k≤10^6；1≤c≤26；n不能被k整除）——字符串s的长度、被删除子串的长度和字母表前c个字母的数量。 - 第二行包含一个由(n mod k)个小写拉丁字母组成的字符串t，每个字母都是字母表前c个字母之一。 输出： - 输出一个整数——生成字典序最小的t的字符串s的数量模998,244,353的值。 示例： 输入： ``` 3 2 2 a ``` 输出： ``` 6 ``` 输入： ``` 5 3 3 bc ``` 输出： ``` 15 ``` 输入： ``` 34 12 26 codeforces ``` 输出： ``` 988024123 ``` 输入： ``` 5 3 1 aa ``` 输出： ``` 1 ``` 注意： 在第一个示例中，生成字符串t="a"的字符串s有："aaa"、"aab"、"aba"、"abb"、"baa"、"bba"。 在第二个示例中，生成字符串t="bc"的字符串s有："bcabc"、"bcacc"、"bcbbc"、"bcbcc"、"bccbc"、"bcccc"、"caabc"、"cabbc"、"cacbc"、"cbabc"、"cbbbc"、"cbcbc"、"ccabc"、"ccbbc"、"cccbc"。