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.