AT_abc222_e [ABC222E] Red and Blue Tree

[problemUrl]: https://atcoder.jp/contests/abc222/tasks/abc222_e $ 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 $ である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_M $ $ U_1 $ $ V_1 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $

答えを出力せよ。

### 制約 - $ 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 $ - 与えられるグラフは木である - 入力に含まれる値は全て整数である ### Sample Explanation 1 $ 1,3 $ 番目の辺を赤く、$ 2 $ 番目の辺を青く塗ったとき、 - 頂点 $ 2 $ から頂点 $ 3 $ への移動で赤い辺を $ 0 $ 回、青い辺を $ 1 $ 回 - 頂点 $ 3 $ から頂点 $ 2 $ への移動で赤い辺を $ 0 $ 回、青い辺を $ 1 $ 回 - 頂点 $ 2 $ から頂点 $ 1 $ への移動で赤い辺を $ 1 $ 回、青い辺を $ 0 $ 回 - 頂点 $ 1 $ から頂点 $ 4 $ への移動で赤い辺を $ 2 $ 回、青い辺を $ 1 $ 回 それぞれ通過し、全体では赤い辺を $ 3 $ 回、青い辺を $ 3 $ 回通るため、条件を満たします。 !\[図\](https://img.atcoder.jp/ghi/f9b2b199fb6eedaca02e15ff556b72b1.png) この他、$ 1,3 $ 番目の辺を青く、$ 2 $ 番目の辺を赤く塗るときも条件を満たし、これら以外の塗り方は条件を満たさないため、答えは $ 2 $ 通りです。 ### Sample Explanation 2 条件を満たす塗り方が存在しないこともあります。