← 返回题目列表

Codeforces · 1910/I

I. 逆问题

中文机器翻译题面 查看原题

考虑以下问题。

给定一个字符串 $$$s$$$,其中包含 $$$n$$$ 小写拉丁字母和一个整数 $$$k$$$($$$n$$$ 不能被 $$$k$$$ 整除)。每个字母都是字母表中前 $$$c$$$ 字母之一。

应用以下操作,直到字符串的长度小于 $$$k$$$:选择长度恰好为 $$$k$$$ 的字符串的连续子字符串,将其从字符串中删除,并将结果部分粘合在一起而不更改顺序。

设长度小于 $$$k$$$ 的结果字符串为 $$$t$$$。可以得到的按字典顺序最小的字符串 $$$t$$$ 是多少?

你被问到这个问题的逆问题。给定两个整数 $$$n$$$ 和 $$$k$$$($$$n$$$ 不能被 $$$k$$$ 整除)和一个由 ($$$n \bmod k$$$) 个小写拉丁字母组成的字符串 $$$t$$$,计算产生 $$$t$$$ 作为字典顺序最小解的字符串 $$$s$$$ 的数量。

打印该数字以 $$$998\,244\,353$$$ 为模。

输入

第一行包含三个整数 $$$n、k$$$ 和 $$$c$$$ ($$$1 \le n \le 10^6$$$; $$$2 \le k \le 10^6$$$; $$$1 \le c \le 26$$$; $$$n$$$ 不能被 $$$k$$$整除) — 字符串的长度$$$s$$$,要删除的子字符串的长度以及字母表中第一个字母的数量。

第二行包含字符串 $$$t$$$,由 ($$$n \bmod k$$$) 个小写拉丁字母组成。每个字母都是字母表中前 $$$c$$$ 字母之一。

输出

打印一个整数 - 产生 $$$t$$$ 作为字典顺序最小解的字符串 $$$s$$$ 的数量。

示例

输入 #1

3 2 2
a

输出 #1

6

输入 #2

5 3 3
bc

输出 #2

15

输入 #3

34 12 26
codeforces

输出 #3

988024123

输入#4

5 3 1
aa

输出#4

1

注意

第一个示例中的字符串 $$$s$$$:“aaa”、“aab”、“aba”、“abb”、“baa”、“bba”。

第二个示例中的字符串 $$$s$$$:"bcabc"、"bcacc"、"bcbbc"、"bcbcc"、"bccbc"、"bcccc"、"caabc"、"cabbc"、"cacbc"、"cbabc"、"cbbbc"、"cbcbc"、"ccabc"、"ccbbc"、"cccbc"。