Inverse KMP

Time limit1sMemory limit1024 MB

Summary

Given a string's KMP prefix-function array and the alphabet size c, count the strings that produce that array, modulo 1e9+7.

Level: Hard8 of 10
Topics: String matching, Combinatorics
Solved: No attempts yet

Problem

bobo has just learnt the Knuth-Morris-Pratt (KMP) algorithm. For a string $S = s_{1} s_{2} \dots s_{n}$ , let $\mathrm{KMP}(S) = (f_2, f_3, \dots, f_n)$ , where $f_i$ is the maximum $j < i$ such that $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 alphabet size, find the number of strings $S$ with $\mathrm{KMP}(S) = (f_2, f_3, \dots, f_n)$ , modulo $(10^9 + 7)$ .

Input

The first line contains two integers $n$ and $c$ , the length of the string and the size of the alphabet ( $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 at least one solution exists.

Output

Print a single integer: the number of strings $S$ that satisfy the condition, modulo $(10^9 + 7)$ .

Examples2

Example 1
Input
```
3 3
0 0
```
Expected output
```
12
```
Example 2
Input
```
5 1000000000
1 2 3 4
```
Expected output
```
1000000000
```