역 KMP

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

요약

알파벳 크기 c와 문자열의 KMP 실패 함수 값이 주어질 때, 같은 값을 만드는 문자열의 개수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

bobo는 방금 Knuth-Morris-Pratt(KMP) 알고리즘을 배웠다. 문자열 $S = s_{1} s_{2} \dots s_{n}$ 에 대해 $\mathrm{KMP}(S) = (f_2, f_3, \dots, f_n)$ 이라고 하자. 여기서 $f_i$ 는 $s_1 s_2 \dots s_j = s_{i-j+1} s_{i-j+2} \dots s_i$ 를 만족하는 $j < i$ 의 최댓값이다. $f_2, f_3, \dots, f_n$ 과 알파벳 크기가 주어질 때, $\mathrm{KMP}(S) = (f_2, f_3, \dots, f_n)$ 을 만족하는 문자열 $S$ 의 개수를 $(10^9 + 7)$ 로 나눈 나머지를 구하라.

입력

첫째 줄에 문자열의 길이 $n$ 과 알파벳 크기 $c$ 가 주어진다( $2 \leq n \leq 2 \cdot 10^5$ , $1 \leq c \leq 10^9$ ). 둘째 줄에 $n - 1$ 개의 정수 $f_2, f_3, \dots, f_n$ 이 주어진다( $0 \leq f_i < i$ ). 해가 적어도 하나 존재함이 보장된다.

출력

조건을 만족하는 문자열 $S$ 의 개수를 $(10^9 + 7)$ 로 나눈 나머지를 한 줄에 출력한다.

예제2

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