Description

You are given positive integers $N$, $K$ and a string $S$ of length $N$ consisting of lowercase English letters.

Let $T$ be the string obtained by concatenating $K$ copies of $S$.

Find the inversion number of the Suffix Array of $T$, modulo $998244353$.

For a string $s$ of length $n$, the suffix array of $s$ is a permutation of integers from $1$ to $n$ that represents the starting positions of all non-empty suffixes of $s$, sorted in lexicographical order.

Input Format

The input is given in the following format:

• $1 \leq N \leq 200\,000$
• $1 \leq K \leq 10^{12}$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $N$ and $K$ are integers.

Output Format

Output the answer in a single line.

4 2
icpc

18

13 92025
jagsummercamp

996562345