31349번 - Inverse KMP 다국어

문제

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.

제한

힌트