题目描述

给定一个包含 $N$ 个顶点的树结构、长度为 $M$ 的序列 $A=(A_1,...,A_M)$ 以及整数 $K$。树的顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。

现在需要将这棵树的 $N-1$ 条边分别染成红色或蓝色（共有 $2^{N-1}$ 种染色方案），求满足以下条件的染色方案数（结果对 $998244353$ 取模）：

条件：

1. 初始时棋子位于顶点 $A_1$
2. 对于 $i=1,...,M-1$ ，将棋子沿最短路径从 $A_i$ 移动到 $A_{i+1}$
3. 设最终红色边被经过的总次数为 $R$，蓝色边为 $B$，需满足 $R-B=K$

输入格式

输入数据格式如下：

$N$ $M$ $K$

$A_1$ $A_2$ $\dots$ $A_M$

$U_1$ $V_1$

$\dots$

$U_{N-1}$ $V_{N-1}$

输出格式

输出满足条件的染色方案数。

输入输出样例

样例1输入：

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

样例1输出：

2

说明：存在两种染色方案满足$R-B=0$（具体方案见原题说明）

样例2输入：

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

样例2输出：

0

说明：不存在满足$R-B=10000$的染色方案

样例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

数据范围

• $2 \leq N \leq 1000$
• $2 \leq M \leq 100$
• $|K| \leq 10^5$
• $1 \leq A_i \leq N$
• 保证输入构成一棵树
• 所有输入均为整数