教我KMP

题目描述

小 R 老师最近在给同学们讲 KMP。

但是讲着讲着，小 R 老师突然发现：自己好像也不是很会 KMP。

小 R 老师坚信，机房里的同学们都是字符串大师。哪怕原串已经灰飞烟灭，只剩下一串神秘的 KMP 前缀函数，同学们也一定能把可能的原串数量全部数出来。

为了掩盖自己不会 KMP 这件事，小 R 老师拿出了一台神秘的字符串机器。对于任意一个字符串 $S$，这台机器都可以输出它的 KMP 前缀函数。

对于一个长度为 $n$ 的字符串 $S=s_1s_2\ldots s_n$，定义 $f_i$ 表示 $S$ 的前缀 $S[1,i]$ 的最长真 border 长度。也就是说，$f_i$ 是最大的整数 $j$，满足：

$$0\le j<i$$

且

$$s_1s_2\ldots s_j=s_{i-j+1}s_{i-j+2}\ldots s_i。$$

特别地，若不存在非空真 border，则 $f_i=0$。

现在，小 R 老师不小心把原来的字符串 $S$ 弄丢了，只留下了这台机器输出的 $f_2,f_3,\ldots,f_n$。

给定一个字符集大小 $c$，也就是说每个字符都可以从 $c$ 种不同字符中选择。小 R 老师想知道：有多少个长度为 $n$ 的字符串 $S$，能够让这台机器输出恰好为给定的 KMP 前缀函数序列？

由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

题目保证给定的 KMP 前缀函数序列至少对应一个合法字符串。

输入格式

第一行包含两个整数 $n,c$，分别表示字符串长度和字符集大小。

第二行包含 $n-1$ 个整数 $f_2,f_3,\ldots,f_n$，表示给定的 KMP 前缀函数。

输出格式

输出一个整数，表示满足条件的字符串数量对 $10^9+7$ 取模后的结果。

样例 1 输入

3 3
0 0

样例 1 输出

12

样例 1 解释

设字符串为 $s_1s_2s_3$。

由于 $f_2=0$，所以必须有：

$$s_2\ne s_1。$$

由于 $f_3=0$，所以必须有：

$$s_3\ne s_1。$$

因此，$s_1$ 有 $3$ 种选择，$s_2$ 有 $2$ 种选择，$s_3$ 有 $2$ 种选择。

所以答案为：

$$3\times 2\times 2=12。$$

样例 2 输入

5 1000000000
1 2 3 4

样例 2 输出

1000000000

样例 2 解释

给定的前缀函数表示：

$$f_2=1,\quad f_3=2,\quad f_4=3,\quad f_5=4。$$

因此每个位置都必须与前一个位置保持连续匹配，整个字符串只能由同一种字符组成。

第一个字符有 $10^9$ 种选择，所以答案为 $10^9$。

样例 3

见选手目录下的 kmp/kmp3.in 与 kmp/kmp3.ans。

该样例满足测试点 $1\sim 12$ 的约束条件。

样例 4

见选手目录下的 kmp/kmp4.in 与 kmp/kmp4.ans。

该样例满足测试点 $1\sim 12$ 的约束条件。

样例 5

见选手目录下的 kmp/kmp5.in 与 kmp/kmp5.ans。

该样例满足测试点 $21\sim 32$ 的约束条件。

样例 6

见选手目录下的 kmp/kmp6.in 与 kmp/kmp6.ans。

该样例满足测试点 $33\sim 64$ 的约束条件。

样例 7

见选手目录下的 kmp/kmp7.in 与 kmp/kmp7.ans。

该样例满足测试点 $33\sim 64$ 的约束条件。

样例 8

见选手目录下的 kmp/kmp8.in 与 kmp/kmp8.ans。

该样例满足测试点 $65\sim 100$ 的约束条件。

样例 9

见选手目录下的 kmp/kmp9.in 与 kmp/kmp9.ans。

该样例满足测试点 $65\sim 100$ 的约束条件。

数据范围

对于所有测试数据，均满足：

• $2\le n\le 10^6$；
• $1\le c\le 10^9$；
• 对于所有 $2\le i\le n$，有 $0\le f_i<i$；
• 题目保证给定的 $f_2,f_3,\ldots,f_n$ 至少对应一个合法字符串。

本题共 $100$ 个测试点，每个测试点 $1$ 分。

测试点编号	分值	约束条件
$1\sim 12$	$12$	$n\le 13,\ c\le 3$
$13\sim 20$	$8$	对所有 $i\ge 2$，均有 $f_i=i-1$
$21\sim 32$	$12$	对所有 $i\ge 2$，均有 $f_i=0$
$33\sim 64$	$32$	$n\le 3000$
$65\sim 100$	$36$	无额外限制