配点 : $500$ 点

問題文

$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$ とすると、$R-B=K$ である。

制約

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

出力

答えを出力せよ。

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

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$ 通りです。

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