P7525 Shelter

 > It's a long way forward, so trust in me > > I'll give them shelter, like you've done for me > > And I know, I'm not alone > > You'll be watching over us, until you're gone

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$.

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 one integer in one line, representing the length of the string after $K$ days modulo $998244353$.

### 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