E. 量词（Quantifier）

题目描述

给定一棵有 $n+1$ 个节点的有根树，节点编号为 $0$ 到 $n$，根节点为 $0$，且根节点唯一的孩子是节点 $1$。

有 $m$ 个互不相同的芯片，编号为 $1$ 到 $m$，每个芯片为黑色或白色。初始时，所有芯片按编号从小到大从上到下依次摆放在边 $(0,1)$ 上。

你可以以任意顺序执行任意次数（包括 $0$ 次）以下操作：

1. 选择两条边 $(u,v)$ 和 $(v,w)$，满足 $u$ 是 $v$ 的父节点、$v$ 是 $w$ 的父节点，且边 $(u,v)$ 上至少有一个芯片。将 $(u,v)$ 上最下方的芯片移动到 $(v,w)$ 上最上方（即放在该边现有所有芯片的上方）。
2. 选择两条边 $(u,v)$ 和 $(v,w)$，满足 $u$ 是 $v$ 的父节点、$v$ 是 $w$ 的父节点，且边 $(v,w)$ 上至少有一个芯片。将 $(v,w)$ 上最上方的芯片移动到 $(u,v)$ 上最下方（即放在该边现有所有芯片的下方）。
3. 选择同一条边上两个颜色相同的相邻芯片，交换它们的位置。

每个芯片 $i$ 都有一个移动范围：定义为从根节点到节点 $d_i$ 的简单路径上的所有边。 在操作过程中，必须保证任何芯片不会被移动到它的移动范围之外。

最后，你必须将所有芯片移回边 $(0,1)$ 上。可以证明，芯片的顺序可能发生改变。 计算芯片最终在边 $(0,1)$ 上的可能排列数量，答案对 $998244353$ 取模。

芯片的排列定义为：从上到下的芯片编号组成的长度为 $m$ 的序列。

输入格式

每个测试包含多组数据。 第一行一个整数 $t$（$1\le t\le 5000$），表示测试用例数量。

每组测试用例：

• 第一行两个整数 $n,m$（$1\le n,m\le 5000$），分别表示树的大小减一（树总共有 $n+1$ 个节点）和芯片数量。
• 第二行 $n$ 个整数 $p_1,p_2,\dots,p_n$（$0\le p_i<i$），表示节点 $1$ 到 $n$ 的父节点。保证 $p_i=0$ 当且仅当 $i=1$（根唯一孩子是 $1$）。
• 第三行 $m$ 个整数 $c_1,c_2,\dots,c_m$（$c_i\in\{0,1\}$），表示芯片颜色，$0$ 为黑色，$1$ 为白色。
• 第四行 $m$ 个整数 $d_1,d_2,\dots,d_m$（$1\le d_i\le n$），表示每个芯片的移动范围终点。

保证：

• 所有测试用例的 $\sum n\le 5000$
• 所有测试用例的 $\sum m\le 5000$

输出格式

对于每组测试用例，输出一行一个整数，表示合法的最终排列数量，对 $998244353$ 取模。

输入样例

4
3 2
0 1 1
0 1
2 3
4 4
0 1 1 2
0 0 1 1
1 2 3 3
6 6
0 1 1 1 4 5
0 0 0 0 1 1
5 6 1 2 4 3
16 15
0 1 1 3 1 3 4 3 3 7 1 6 11 5 8 10
1 0 1 1 0 1 1 1 1 0 1 1 0 0 0
12 14 13 10 9 16 11 14 13 15 16 10 2 2 5

输出样例

2
8
108
328459046

样例解释

• 第一个测试用例：最终可以得到 $2$ 种合法排列：$(1,2)$ 和 $(2,1)$。
• 第二个测试用例：最终可以得到 $8$ 种合法排列。