33369번 - Hardcore String Counting 다국어

문제

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 prime number 998ドル,244円,353円 = 2^{23} \cdot 119 + 1$.

입력

The first line of the input contains two integers: $n,ドル the length of $s,ドル and $m,ドル the length of strings you have to count (1ドル \leq n \leq 10^5,ドル $n \leq m \leq 10^9$). The second line contains a string $s$ consisting of $n$ lowercase English letters.

출력

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

제한

힌트