题目描述

给出 $n$ 个点的树和长度为 $m$ 的序列 $a$。现需要给每条边染成红色（red）或者蓝色（blue），要求按照 $a$ 走的路径，经过的边数 红色 $−$ 蓝色 $=k$，问方案数。对 $998244353$ 取模。

按照 $a$ 走的路径是，按照 $a_1\to a_2\to a_3\to \cdots \to a_m$ 的方式移动。

输入格式

第一行输入三个整数 $n,m,k$

第二行输入 $m$ 个整数代表 $a_1,a_2,\cdots,a_m$

接下来 $n-1$ 行每行两个整数 $u,v$ 代表树的一条边。

输出格式

输出方案数

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

2

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

0

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

126

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

2

提示

• $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$

样例解释 1

如果我们将第 $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

无论怎么染色都无法满足条件。