#abc222e. [abc222_e]Red and Blue Tree

[abc222_e]Red and Blue Tree

問題文

NN 頂点の木と、長さ MM の数列 A=(A1,ldots,AM)A=(A_1,\\ldots,A_M)、整数 KK が与えられます。
木の頂点には 11 から NN の番号がつけられており、ii 番目の辺は頂点 UiU_iViV_i を結んでいます。

この木の N1N-1 個の辺をそれぞれ赤か青のどちらかに塗ります。そのような方法は 2N12^{N-1} 通りありますが、そのうち次の条件を満たすような塗り方の個数を 998244353998244353 で割った余りを求めてください。

条件:
最初、駒を頂点 A1A_1 におく。i=1,ldots,M1i=1,\\ldots,M-1 の順に、駒を頂点 AiA_i から頂点 Ai+1A_{i+1} まで、辺をたどって最短経路で動かす。 これらの操作を最後まで行ったとき、赤く塗られた辺を通過した回数を RR、青く塗られた辺を通過した回数を BB とすると、RB=KR-B=K である。

制約

  • 2leqNleq10002 \\leq N \\leq 1000
  • 2leqMleq1002 \\leq M \\leq 100
  • Kleq105|K| \\leq 10^5
  • 1leqAileqN1 \\leq A_i \\leq N
  • 1leqUi,VileqN1\\leq U_i,V_i\\leq N
  • 与えられるグラフは木である
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

NN MM KK A1A_1 A2A_2 ldots\\ldots AMA_M U1U_1 V1V_1 vdots\\vdots UN1U_{N-1} VN1V_{N-1}

出力

答えを出力せよ。


入力例 1

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

出力例 1

1,31,3 番目の辺を赤く、22 番目の辺を青く塗ったとき、

  • 頂点 22 から頂点 33 への移動で赤い辺を 00 回、青い辺を 11
  • 頂点 33 から頂点 22 への移動で赤い辺を 00 回、青い辺を 11
  • 頂点 22 から頂点 11 への移動で赤い辺を 11 回、青い辺を 00
  • 頂点 11 から頂点 44 への移動で赤い辺を 22 回、青い辺を 11

それぞれ通過し、全体では赤い辺を 33 回、青い辺を 33 回通るため、条件を満たします。

図

この他、1,31,3 番目の辺を青く、22 番目の辺を赤く塗るときも条件を満たし、これら以外の塗り方は条件を満たさないため、答えは 22 通りです。


入力例 2

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

出力例 2

条件を満たす塗り方が存在しないこともあります。


入力例 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