AT_jsc2023_final_g Fusion

$ 1 $ から $ N $ までの番号のついた $ N $ 頂点からなる木 $ T $ があります． $ i $ 番目の辺は頂点 $ A_i $ と $ B_i $ を結んでいます． また，各頂点には整数が書かれており，頂点 $ i $ に書かれている整数は $ V_i $ です． あなたは今から以下の操作を $ N-1 $ 回行います． - $ T $ の辺を $ 1 $ つ選び，縮約する． 縮約前の $ 2 $ つの頂点に書かれていた整数を $ x,y $ とおき，縮約後の頂点には $ x \times y+1 $ を書き込む． 操作を行う方法は $ (N-1)! $ 通りあります． 全ての方法について，最終的に残る $ 1 $ 頂点に書かれた値を求めたとします． これら $ (N-1)! $ 個の値の総和を $ 998244353 $ で割った余りを求めてください． 辺の縮約とはグラフ $ G $ について，辺 $ (u,v) $ を縮約する操作とは，頂点 $ u,v $ を $ 1 $ つの頂点にまとめる操作です． より正確には，縮約とは $ G $ を以下のように変化させる操作です． - $ G $ から辺 $ (u,v) $ および頂点 $ u,v $ を削除し，新しい頂点 (これを $ w $ と呼ぶ) を追加する． - $ u $ に接続する各辺 $ (u,x) $ を削除し，変わりに辺 $ (w,x) $ を追加する． - $ v $ に接続する各辺 $ (v,x) $ を削除し，変わりに辺 $ (w,x) $ を追加する．

入力は以下の形式で標準入力から与えられる． > $ N $ $ V_1 $ $ V_2 $ $ \cdots $ $ V_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

答えを出力せよ．

### Sample Explanation 1 操作を行う方法は以下の $ 2 $ 通りあります． - 最初の操作で辺 $ (1,2) $ を選んだ場合，縮約後の頂点には $ 1 \times 2+1=3 $ が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 $ 3 $ を縮約します． すると， $ 3 \times 3+1=10 $ が書かれた頂点が残ります． - 最初の操作で辺 $ (3,2) $ を選んだ場合，縮約後の頂点には $ 3 \times 2+1=7 $ が書き込まれます． 次の操作では，縮約によってできた頂点と頂点 $ 1 $ を縮約します． すると， $ 7 \times 1+1=8 $ が書かれた頂点が残ります． よって求める答えは $ 10+8=18 $ です． ### Constraints - $ 1 \leq N \leq 5000 $ - $ 1 \leq V_i < 998244353 $ - $ 1 \leq A_i,B_i \leq N $ - 入力されるグラフは木． - 入力される値はすべて整数．