说明

给定正整数 $N$、$K$ 和一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。

令 $T$ 为将 $S$ 重复 $K$ 次连接得到的字符串。

求 $T$ 的后缀数组的逆序数，对 $998244353$ 取模。

对于一个长度为 $n$ 的字符串 $s$，$s$ 的后缀数组是一个从 $1$ 到 $n$ 的整数排列，它表示 $s$ 的所有非空后缀的起始位置，并按字典序排序。

输入格式

输入格式如下：

• $1 \leq N \leq 200\,000$
• $1 \leq K \leq 10^{12}$
• $S$ 是一个长度为 $N$ 的字符串，由小写英文字母组成。
• $N$ 和 $K$ 是整数。

输出格式

在一行中输出答案。

4 2
icpc

18

13 92025
jagsummercamp

996562345

提示

翻译由 DeepSeek V3.2 完成