Problem Description

In space, Rin not only freely creates in the virtual world but also plays a fun 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 a length of \( n \). Each day, Rin finds the largest integer \( i \) (\( 0 \le i < |s| \)) such that the prefix of length \( i \) is the same as the suffix of length \( i \) (note that \( i \) may be \( 0 \)), and appends this prefix/suffix to the end of the 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 to form the new string mivikismivikmivik.

After \( K \) days in space, the string has become very long. Rin suddenly wonders what the length of this string is now. Can you help her? Since the answer may be very large, you only need to tell her the result modulo \( 998244353 \).

Input Format

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

The second line contains a string \( s \) of length \( n \) consisting of lowercase English letters, representing the string left by Rin's father.

Output Format

A single line containing an integer representing the length of the string after \( K \) days modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

7 1
abcdabc

Sample Output #1

10

Sample Input #2

5 2
ioioi

Sample Output #2

11

Sample Input #3

8 50
idolidol

Sample Output #3

263923940

Notes

Sample Explanation

Sample 1: After one operation, the string becomes abcdabcabc, with a length of \( 10 \).

Sample 2: After one operation, the string becomes ioioiioi, and after another operation, it becomes ioioiioiioi, with a length of \( 11 \).

Data Range

For all data, \( 1 \le n \le 2 \cdot 10^6 \) and \( 1 \le K \le 10^{18} \).

Subtask 1 (15 pts): Guaranteed that \( s \) consists of only one type of letter.

Subtask 2 (20 pts): Guaranteed that \( s \) has an integer period that is not equal to \( |s| \) (i.e., a period that is a divisor of \( |s| \)).

Subtask 3 (65 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分