问题描述

给定一个具有 $N$ 个顶点的树，一个由 $M$ 个数字 $A=(A_1,\\ldots,A_M)$ 组成的序列，以及一个整数 $K$。
顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。

我们将这棵树的 $N-1$ 条边中的每一条都涂成红色或蓝色。在 $2^{N-1}$ 种方式中，找到满足以下条件的数量，对 $998244353$ 取模。

条件：
让我们把一个棋子放在顶点 $A_1$ 上，并按照顺序对每个 $i=1,\\ldots,M-1$，沿着最短路径从顶点 $A_i$ 移动到顶点 $A_{i+1}$。移动结束后，满足 $R-B=K$，其中 $R$ 和 $B$ 分别是棋子经过红色边和蓝色边的次数。

约束条件

• $2 \\leq N \\leq 1000$
• $2 \\leq M \\leq 100$
• $|K| \\leq 10^5$
• $1 \\leq A_i \\leq N$
• $1\\leq U_i,V_i\\leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

---

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $K$ $A_1$ $A_2$ $\\ldots$ $A_M$ $U_1$ $V_1$ $\\vdots$ $U_{N-1}$ $V_{N-1}$

输出

输出答案。

---

示例输入 1

4 5 0
2 3 2 1 4
1 2
2 3
3 4

示例输出 1

2

如果我们将第 $1$ 条和第 $3$ 条边涂成红色，将第 $2$ 条边涂成蓝色，棋子经过以下数量的红色和蓝色边：

• 当从顶点 $2$ 移动到 $3$ 时，经过 $0$ 条红色边和 $1$ 条蓝色边，
• 当从顶点 $3$ 移动到 $2$ 时，经过 $0$ 条红色边和 $1$ 条蓝色边，
• 当从顶点 $2$ 移动到 $1$ 时，经过 $1$ 条红色边和 $0$ 条蓝色边，
• 当从顶点 $1$ 移动到 $4$ 时，经过 $2$ 条红色边和 $1$ 条蓝色边，

总共经过 $3$ 条红色边和 $3$ 条蓝色边，满足条件。

满足条件的另一种方式是将第 $1$ 条和第 $3$ 条边涂成蓝色，将第 $2$ 条边涂成红色。没有其他满足条件的方法，因此答案是 $2$。

---

示例输入 2

3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

示例输出 2

0

可能没有办法涂色以满足条件。

---

示例输入 3

10 2 -1
1 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

示例输出 3

126

---

示例输入 4

5 8 -1
1 4 1 4 2 1 3 5
1 2
4 1
3 1
1 5

示例输出 4

2