bobo 刚刚学习了 Knuth-Morris-Pratt (KMP) 算法。

对于字符串 $S = s_1s_2 \dots s_n$，定义 $\text{KMP}(S) = (f_2, f_3, \dots, f_n)$，其中 $f_i$ 是满足 $s_1s_2 \dots s_j = s_{i-j+1}s_{i-j+2} \dots s_i$ 的最大整数 $j < i$。

给定 $f_2, f_3, \dots, f_n$ 以及字母表的大小 $c$，求满足 $\text{KMP}(S) = (f_2, f_3, \dots, f_n)$ 的字符串 $S$ 的数量，结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $c$，分别表示字符串的长度和字母表的大小 ($2 \le n \le 10^5, 1 \le c \le 10^9$)。

第二行包含 $(n - 1)$ 个整数 $f_2, f_3, \dots, f_n$ ($0 \le f_i < i$)。

保证至少存在一个解。

输出格式

输出一个整数，表示字符串的数量。

样例

样例输入 1

3 3
0 0

样例输出 1

12

样例输入 2

5 1000000000
1 2 3 4

样例输出 2

1000000000