给定一棵有根树,其中 $$$n+1$$$ 节点标记为从 $$$0$$$ 到 $$$n$$$,其中根是节点 $$$0$$$,并且 它唯一的子节点是节点 $$$1$$$。有$$$m$$$ 不同 芯片标记为从 $$$1$$$ 到 $$$m$$$,每个颜色为黑色或白色。最初,它们按照标签升序从上到下排列在边缘 $$$(0,1)$$$ 上。
筹码的初始位置。树节点以蓝色显示。 您可以按任意顺序执行以下操作任意次数(可能为零):
- 选择两条边 ($$$u,v$$$) 和 ($$$v,w$$$),使得 $$$u$$$ 是 $$$v$$$ 的父级,$$$v$$$ 是 $$$w$$$ 的父级,其中边 ($$$u,v$$$) 至少包含一个码片。移动 最底部 边缘芯片 ($$$u,v$$$) 到 最上面 放置在边缘 ($$$v,w$$$),i。 即,首先是 ($$$v,w$$$) 上的所有现有筹码。
- 选择两条边 ($$$u,v$$$) 和 ($$$v,w$$$),使得 $$$u$$$ 是 $$$v$$$ 的父级,$$$v$$$ 是 $$$w$$$ 的父级,其中边 ($$$v,w$$$) 至少包含一个码片。移动 最上面 边缘芯片 ($$$v,w$$$) 到 最底部 放置在边缘 ($$$u,v$$$),i。 即,位于 ($$$u,v$$$) 上所有现有筹码下方。
- 选择两个 相邻 相同颜色的筹码位于同一边缘,并交换位置。
允许的操作。 每个芯片 $$$i$$$ 都有一个移动范围,定义为从根到节点 $$$d_i$$$ 的简单路径上的所有边。操作过程中,必须保证切屑不会移动到其移动范围之外的边缘。
最后,您必须将所有筹码移回边缘 $$$(0,1)$$$。可以发现芯片的顺序可能会改变。计算边缘 $$$(0,1)$$$ 对 $$$998\,244\,353$$$ 取模后最终排列的码片的可能排列数。
码片排列定义为长度为 $$$m$$$ 的序列,其中包含 标签 芯片从上到下。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 5000$$$) - 树的大小减一(即,树有 $$$n+1$$$ 节点)和芯片数。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \lt i$$$) - 从 $$$1$$$ 到 $$$n$$$ 的节点的父节点。当且仅当 $$$i = 1$$$(根的唯一子节点是节点 $$$1$$$)时,保证 $$$p_i = 0$$$。
第三行包含 $$$m$$$ 整数 $$$c_1, c_2, \ldots, c_m$$$ ($$$c_i \in \{0, 1\}$$$) — 每个芯片的颜色($$$0$$$ 为黑色,$$$1$$$ 为白色)。
第四行包含 $$$m$$$ 整数 $$$d_1, d_2, \ldots, d_m$$$ ($$$1\le d_i \le n$$$) — 每个筹码的移动范围。
保证所有测试用例中 $$$n$$$ 的总和不超过 $$$5000$$$,并且 $$$m$$$ 的总和不超过 $$$5000$$$。
输出
对于每个测试用例,输出一个整数 - 芯片的可能排列数以 $$$998\,244\,353$$$ 为模。
示例
输入复制
43 20 1 10 12 34 40 1 1 20 0 1 11 2 3 36 60 1 1 1 4 50 0 0 0 1 15 6 1 2 4 316 150 1 1 3 1 3 4 3 3 7 1 6 11 5 8 101 0 1 1 0 1 1 1 1 0 1 1 0 0 012 14 13 10 9 16 11 14 13 15 16 10 2 2 5
输出复制
2 8 108 328459046
注意
在第一个测试用例中,我们可以达到以下 $$$2$$$ 排列:($$$1,2$$$) 和 ($$$2,1$$$)。
在第二个测试用例中,我们可以达到以下 $$$8$$$ 排列: ($$$1,2,3,4$$$), ($$$1,2,4,3$$$), ($$$1,3,2,4$$$), ($$$1,3,4,2$$$), ($$$1,4,2,3$$$), ($$$1,4,3,2$$$)、($$$2,1,3,4$$$) 和 ($$$2,1,4,3$$$)。