Hardcore String Counting

Time limit8sMemory limit2048 MB

Summary

Count strings of length m over 26 letters where s first appears as a substring at the very end, modulo 998244353, with n up to 1e5 and m up to 1e9.

Level: Hard9 of 10
Topics: String matching, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You are given a non-empty string $s$ of lowercase English letters. A string $w$ of lowercase English letters is good if every proper prefix of $w$ does not contain $s$ as a substring, but $w$ itself does.

Find the number of good strings of length $m$ . Because this number can be very large, output it modulo the prime number $998\,244\,353 = 2^{23} \cdot 119 + 1$ .

Input

The first line contains two integers $n$ , the length of $s$ , and $m$ , the length of the strings to count ( $1 \leq n \leq 10^5$ , $n \leq m \leq 10^9$ ). The second line contains the string $s$ , which consists of $n$ lowercase English letters.

Output

Output a single nonnegative integer: the number of good strings of length $m$ modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
6 7
aaaaaa
```
Expected output
```
25
```
Example 2
Input
```
3 5
aba
```
Expected output
```
675
```