I. String Duplication
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little H initially has a string $$$s$$$ composed of lowercase letters.

The charm value of a string is defined as the number of essentially different substrings.

For example, $$$\texttt{aaa}$$$ has only $$$3$$$ essentially different substrings: $$$\texttt{a}, \texttt{aa}, \texttt{aaa}$$$, while $$$\texttt{aabb}$$$ has $$$8$$$ essentially different substrings: $$$\texttt{a}, \texttt{aa}, \texttt{b}, \texttt{bb}, \texttt{ab}, \texttt{aab}, \texttt{abb}, \texttt{aabb}$$$.

He thinks the charm value of the initial string $$$s$$$ is too low, so he duplicates $$$s$$$ $$$m$$$ times and concatenates them together, trying to obtain a string with a higher charm value.

However, after he finished duplicating, he found that he could not accurately calculate its charm value. Please help him calculate the charm value of the duplicated string. Since the answer may be large, you need to output the charm value modulo $$$998244353$$$.

Input

The first line contains two integers $$$n,m$$$ $$$(1 \leq n \leq 3 \times 10^5, 1 \leq m \leq 10^9)$$$, representing the length of the string $$$s$$$ and the number of duplications.

The second line contains a string $$$s$$$ composed of lowercase letters.

Output

Output a single integer, representing the result of the charm value modulo $$$998244353$$$.

Examples
Input
6 2
mantle
Output
57
Input
12 1919810
ifamjlifamjl
Output
138226305
Input
13 935330878
aabbbbababbaa
Output
348310505