A省には合計 $n$ 個の都市があり、都市間は $n-1$ 本の道路で結ばれ、木を構成している。

各都市 $i$ は非負整数の魅力値 $w_i$ を持つ。都市からなる連結部分グラフ $S$ について、その魅力値の平均が $1$ である、すなわち $\frac 1{|S|} \sum_{u\in S} w_u = 1$ を満たすとき、この連結部分グラフを調和的であると呼ぶ。

各都市の具体的な魅力値は不明であるが、都市 $i$ の魅力値は $0$ から $a_i$ までの整数から一様にランダムに選ばれることがわかっている。

A省において、調和的な連結部分グラフの個数の期待値を求めよ。期待値に $\prod_{i=1}^n (a_i+1)$ を掛けた値を求め、その値を $998244353$ で割った余りを出力せよ。

入力

第一行に正整数 $n$ が与えられる。これは都市の数を表す。

第二行に $n$ 個の正整数が与えられ、順に $a_i$ を表す。

続く $n-1$ 行には、各行に二つの正整数 $u, v$ が与えられ、辺を表す。

出力

答えとなる整数を一行に出力せよ。

入出力例

入力 1

2
1 2
1 2

出力 1

7

注記 1

• $w_1=1$ のとき、$\{1\}$ は調和的であり、これは $\frac 12$ の確率で発生する。
• $w_2=1$ のとき、$\{2\}$ は調和的であり、これは $\frac 13$ の確率で発生する。
• $w_1=w_2=1$ または $w_1=0, w_2=2$ のとき、$\{1, 2\}$ は調和的であり、これは $\frac 13$ の確率で発生する。

したがって、調和的な連結部分グラフの期待値の合計は $\frac 12 + \frac 13 + \frac 13 = \frac 76$ である。

入力 2

3
2 1 3
1 2
1 3

出力 2

46

制約

すべてのデータにおいて、$1\le n\le 3000$ を満たす。すべての $1\le i\le n$ について $1\le a_i\le n$ であり、入力される $u, v$ は木を構成する。

• テストケース $1\sim 3$: $n\le 50$ を満たす。
• テストケース $4\sim 5$: $\sum a_i \le 5000$ を満たす。
• テストケース $6\sim 7$: 木はパスグラフであり、$v=u+1$ を満たす。
• テストケース $8$: $a_i=n$ を満たす。
• テストケース $9\sim 10$: 特殊な制約はない。