题目描述

有一棵 $N$ $(1 \leq N \leq 2\times 10^4)$ 个节点的有根树，每个节点可以填 $0\sim9$。

有 $M$ $(1 \leq M \leq 5\times 10^4)$ 个限制，限制了从 $X$ 开始往祖先跳的的包含 $X$ 的 $5$ 个节点（保证 $X$ 上面一定存在这样一条路径,也就是说 $X$ 的深度至少为 $5$），一定不是 $ABCDE$。

请你求出，根据这 $M$ 个限制，共有多少种给这棵树全部填上数的方案一定是不可能的。

输入格式

第 $1$ 行：两个用空格分隔的整数 $N$ 和 $M$。

第 $2\sim N$ 行：第 $i+1$ 行包含一个整数 $p_i$，表示树中节点 $i$ 的父节点，满足 $0\leq p_i<i$。

第 $N+1\sim N+M$ 行：第 $N+i$ 行描述第 $i$ 个禁止出现的序列。该行包含用空格分隔的 $v_i$ 和 $s_i$，其中 $v_i$ 是该序列的起始节点，$s_i$ 是一个 $5$ 位字符串，已知从 $v_i$ 开始向上遍历树得到的 $5$ 个节点的数字序列，不能等于 $s_i$ 对应的序列。题目保证从 $v_i$ 向上至少有 $5$ 个节点。

输出格式

一行一个整数，表示被排除的不合法配置数量，结果对 $1234567$ 取模。

6 2 
0 
1 
2 
3 
3 
4 01234 
5 91234 

19