Description

During her time in space, besides creating freely in the virtual world, Rin also plays an interesting little game every day.

When she first arrived in space, her father left her a non-empty string $s$ consisting of lowercase English letters, with length $n$. Every day, Rin finds the largest integer $i$ ($0 \le i < |s|$) such that the prefix of length $i$ and the suffix of length $i$ of the string are the same (note that $i$ may be $0$), and then appends this prefix/suffix to the end of the whole string to form a new string. For example, when the string is mivikismivik, the largest $i = 5$ (both the prefix and suffix of length $5$ are mivik), so Rin appends mivik to the end of the string, forming the new string mivikismivikmivik.

After spending $K$ days in space, this string has become very long. Rin is suddenly curious about what the length of the string is now. Can you help her? Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains two positive integers $n, K$, representing the length of the initial string and the number of days Rin has spent in space.

The second line contains a string $s$ of length $n$ consisting of lowercase English letters, representing the string left to Rin by her father.

Output Format

Output one integer in one line, representing the length of the string after $K$ days modulo $998244353$.

7 1
abcdabc

10

5 2
ioioi

11

8 50
idolidol

263923940

Hint

Sample Explanation

Sample 1: After one operation, the string becomes abcdabcabc, with length $10$.

Sample 2: After one operation, the string becomes ioioiioi, and after another operation it becomes ioioiioiioi, with length $11$.

Constraints

For all testdata, $1 \le n \le 2 \cdot 10^6$, $1 \le K \le 10^{18}$.

Subtask 1 (15 pts): $s$ consists of only one kind of letter.

Subtask 2 (20 pts): $s$ has a proper period whose length is not $|s|$ (i.e. a period whose length is a divisor of $|s|$).

Subtask 3 (65 pts): No special constraints.

Translated by ChatGPT 5