Inverse KMP

시간 제한1초메모리 제한1024 MB

요약

길이 n인 문자열의 KMP 실패 함수와 알파벳 크기 c가 주어질 때, 그 실패 함수를 정확히 만드는 문자열의 개수를 10^9+7로 나눈 나머지로 구한다.

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

문제

bobo has just learnt Knuth-Morris-Pratt (KMP) algorithm.

For string $S = s\_{1} s\_{2} \dots s\_{n}$ , $\mathrm{KMP}(S) = (f\_2, f\_3, \dots, f\_n)$ where $f\_i$ is the maximum $j < i$ where $s\_{1} s\_{2} \dots s\_{j} = s\_{i - j + 1} s\_{i - j + 2} \dots s\_{i}$ .

Given $f\_2, f\_3, \dots, f\_n$ and the size of alphabet, find out the number of strings $S$ where $\mathrm{KMP}(S) = (f\_2, f\_3, \dots, f\_n)$ modulo $(10^9 + 7)$ .

입력

The first line contains $2$ integers $n$ and $c$ , which denotes the length of the string and the size of alphabet, respectively ( $2 \leq n \leq 2 \cdot 10^5, 1 \leq c \leq 10^9$ ).

The second line contains $(n - 1)$ integers $f\_2, f\_3, \dots, f\_n$ ( $0 \leq f\_i < i$ ).

It is guaranteed that there exists at least one solution.

출력

A single integer denotes the number of strings.

예제2

예제 1
입력
```
3 3
0 0
```
예상 출력
```
12
```
예제 2
입력
```
5 1000000000
1 2 3 4
```
예상 출력
```
1000000000
```