考虑以下问题。
给定一个字符串 $$$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"。