警察局 2099

时间限制：1秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

复制人被创造出来是为了执行人类不愿意自己做的工作。这包括非常危险的任务，在《银翼杀手2049》事件之后，这样的任务越来越多。

洛杉矶警察局共有 $n$ 名员工，有着严格的等级制度。顶端是新任警察局长，替代了乔希中尉——编号为 $1$ 的员工，其余 $n-1$ 名员工是复制人，每个复制人都有直接上级 $p_i < i$。因此，员工的等级结构构成一棵以 $1$ 号节点为根的树。

每个员工还有一个专长 $a_i$，用一个从 'a' 到 'z' 的英文字母表示——它描述了该员工最擅长的技能或能力。已知这些专长是随机均匀分布的，即每个员工拥有某个具体专长的概率恰好为 $\frac{1}{26}$，并且与其他员工的专长相互独立。

现在警察局有 $m$ 个至关重要的任务需要紧急处理。由于任务很严峻，不能随意派人去执行：

每个任务需要派遣一个员工序列，其中每个后一个必须是前一个的直接下属；换句话说，这些警察必须构成等级树中的一条垂直路径；
每个任务由一个字符串 $s_i$ 指定，该字符串描述了成功完成该任务所需的专长集合——派遣的警察按军衔从高到低（从等级树的顶部到底部）排序，其专长必须与 $s_i$ 中的字符顺序完全一致。

对于每个 $m$ 个任务，求选择一队可派遣的警察序列的方案数。每个任务的答案需要独立计算。

第一行包含两个整数 $n$ 和 $m$ —— 员工数和任务数（$1 \le n, m \le 4 \cdot 10^5$）。

第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ —— 第 $2$ 到第 $n$ 名员工的直接上级编号（$1 \le p_i < i$）。

第三行包含一个长度为 $n$ 的字符串 $a$，其中第 $i$ 个字符是从 'a' 到 'z' 的字母，表示第 $i$ 名员工的专长。

接下来 $m$ 行，每行一个字符串 $s_i$ —— 每个任务所需的专长序列（$1 \le |s_i| \le 4 \cdot 10^5$）。保证每个 $s_i$ 仅由 'a' 到 'z' 的字母组成。同时保证所有 $s_i$ 的总长度不超过 $10^6$。

对于每个任务，输出一行一个整数，表示在满足条件的情况下，选择 $|s_i|$ 名员工来完成该任务的方案数。

只有通过该子任务及其所需子任务的所有测试，才能获得该子任务分数。

子任务	分数	附加限制	所需子任务	评测信息
0	–	样例	无	完全
1	7	$n, m,	s_i	\le 10$	0	完全
2	18	$p_i = i-1$ 对所有 $i$	无	第一次错误
3	8	$m = 1$；$s_{i,j} = \text{'a'}$ 对所有 $i,j$	无	第一次错误
4	8	$m = 1$	3	第一次错误
5	12	$	s_i	\le 3$ 对所有 $i$	无	第一次错误
6	16	$n, m \le 100$；$	s_i	\le 100$ 对所有 $i$	0, 1	第一次错误
7	6	$n \cdot m \le 10^6$	0, 1, 6	第一次错误
8	25	无	0–7	第一次错误

示例 1

输入

3 4
1 1
aba
aa
ab
ba
bb

输出

示例 2

输入

7 6
1 1 2 3 5 6
aabbaba
aa
ab
ba
aba
ababa
ababab

输出

示例 3

输入

10 4
1 2 3 4 5 6 7 8 9
abacabadab
abacabada
bacabadab
abacabadab
bacabadaba

输出

注意，在样例中，专长的随机性条件被违反了，这些样例是为方便说明而特别选择的。

在其他所有测试中，每个专长都是从 'a' 到 'z' 中均匀随机独立选择的。