g6-07518. 受限独立集计数 未做

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点。每个结点有一个限制 $s_i$：

• $s_i=0$：无限制；
• $s_i=1$：该结点必须选；
• $s_i=2$：该结点不能选。

选择若干结点，要求任意一对父子不能同时被选。求方案数对 $10^9+7$ 取模。

第一行一个整数 $n$。

第二行 $n$ 个整数 $s_1,s_2,\dots ,s_n$。

第三行 $n-1$ 个整数 $f_2,f_3,\dots ,f_n$（$n=1$ 时该行为空）。

一行一个整数。

输入：

2
1 2
1

输出：

1

$1$ 必须选、$2$ 不能选，唯一合法方案是 $\{1\}$。

输入：

3
0 0 0
1 1

输出：

5

空集、$\{1\}$、$\{2\}$、$\{3\}$、$\{2,3\}$。

• 对于 $30\%$ 的测试点，$1\le n\le 20$；
• 对于 $60\%$ 的测试点，$1\le n\le 2000$；
• 对于全部测试点，$1\le n\le 10^5$。