Hardcore String Counting

시간 제한8초메모리 제한2048 MB

요약

길이 m인 소문자 문자열 가운데 주어진 패턴 s가 마지막 문자에서 처음 나타나는 문자열의 개수를 998244353으로 나눈 나머지로 구한다. n은 10^5, m은 10^9까지 주어진다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 동적 계획법, 행렬, 조합론
정답자: 아직 제출이 없습니다

문제

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

예제2

예제 1
입력
```
6 7
aaaaaa
```
예상 출력
```
25
```
예제 2
입력
```
3 5
aba
```
예상 출력
```
675
```