警察局 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输出
1
1
0
0示例 2
输入
7 6
1 1 2 3 5 6
aabbaba
aa
ab
ba
aba
ababa
ababab输出
1
3
2
2
1
0示例 3
输入
10 4
1 2 3 4 5 6 7 8 9
abacabadab
abacabada
bacabadab
abacabadab
bacabadaba输出
1
1
1
0注意
注意，在样例中，专长的随机性条件被违反了，这些样例是为方便说明而特别选择的。
在其他所有测试中，每个专长都是从 'a' 到 'z' 中均匀随机独立选择的。