给你一棵有 $$$n$$$ 个顶点的树。
英雄 $$$k$$$ 次执行以下操作:
- 选择一些边。
- 删除它。
- 取出剩下的两个部分之一并将其删除。
- 在剩余部分写入顶点数。
您将获得一棵初始树和一系列书面数字。找出使所写数字等于给定数字的运算方法的数量。由于答案可能很大,请通过对$$$998\,244\,353$$$求模来找到它。如果在某些操作边缘或剩余部分选择不同,则两种方式被认为是不同的。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5000$$$) — 顶点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$s$$$, $$$f$$$ ($$$1 \leq s, f \leq n$$$, $$$s \neq f$$$) — 边 $$$(s, f)$$$ 的描述。
下一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq \min{(6, n - 1)}$$$) — 操作数。
下一行包含 $$$k$$$ 整数 $$$s_1, s_2, \ldots, s_k$$$ ($$$n > s_1 > s_2 > \ldots > s_k \geq 1$$$) — 书面数字。
输出
打印一个整数 — 问题的答案以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 1 2 2 3 2 2 1
输出 #1
4
输入 #2
7 2 1 3 2 4 1 5 3 6 4 7 4 2 4 2
输出 #2
2
输入 #3
7 1 2 1 3 1 4 2 5 3 6 4 7 1 2
输出 #3
3
输入#4
7 1 2 1 3 1 4 2 5 3 6 4 7 4 6 5 2 1
输出#4
24
输入 #5
8 1 2 2 3 3 4 3 5 3 6 3 7 3 8 2 7 4
输出 #5
0
注意
在第一个测试中,有四种可能的操作方式:
- 删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。删除边 $$$(2, 3)$$$ 并删除顶点 $$$2$$$。
- 删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。
- 删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。删除边 $$$(1, 2)$$$ 并删除顶点 $$$1$$$。
- 删除边 $$$(3, 2)$$$ 并删除顶点 $$$3$$$。删除边 $$$(2, 1)$$$ 并删除顶点 $$$2$$$。
在第二个测试中,有两种可能的操作方式:
- 删除边 $$$(4, 1)$$$ 并删除带有顶点 $$$4$$$ 的部分。删除边 $$$(2, 3)$$$ 并删除带有顶点 $$$2$$$ 的部分。
- 删除边 $$$(4, 1)$$$ 并删除带有顶点 $$$4$$$ 的部分。删除边 $$$(3, 2)$$$ 并删除带有顶点 $$$3$$$ 的部分。