题目描述

给定一棵 $n$ 个点的树，$1$ 号点是树的根，其中一些点已经有了颜色，颜色共三种，以 0，1，2 表示。请为还没有染色的点染色，要求每条边的两个端点颜色不能一样。请计算有多少种可行的方案。由于答案可能很大，输出方案数模 $10^9+7$ 的余数。

输入格式

第一行：两个整数 $n$ 和 $k$； 第二行：$n-1$ 个整数 $p_2,\dots,p_n$ 表示树上 $2$ 号点到 $n$ 号点各自的父亲编号； 接下来 $k$ 行：每行两个整数 $u$ 和 $c$，表示树上 $u$ 号点的颜色为 $c$（$0\leq c\leq 2$）。

输出格式

单个整数：表示染色的方案数模 $10^9+7$ 的余数。

4 1
1 1 1
2 0

8

样例解释 1

只有一个叶子的颜色是确定，根可以有两种颜色，另外两个叶子可以各有两种颜色

数据范围

• 对于 $30\%$ 的数据，$1\leq k\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq k\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq k\leq n\leq 100000$；