Prowincja A składa się z $n$ miast połączonych $n-1$ drogami, tworząc strukturę drzewa.

Każde miasto $i$ posiada nieujemną liczbę całkowitą jako wartość atrakcyjności $w_i$. Spójny podzbiór miast $S$ nazywamy harmonijnym, jeśli średnia wartość atrakcyjności miast w tym zbiorze wynosi $1$, czyli $\frac 1{|S|} \sum_{u\in S} w_u = 1$.

Nie znamy dokładnych wartości atrakcyjności każdego miasta; wiemy jedynie, że wartość atrakcyjności miasta $i$ jest liczbą całkowitą wybraną jednostajnie losowo z przedziału od $0$ do $a_i$.

Oblicz oczekiwaną liczbę harmonijnych spójnych podzbiorów miast w prowincji A. Należy wyprowadzić wynik pomnożony przez $\prod_{i=1}^n (a_i+1)$. Ponieważ wynik może być bardzo duży, należy podać go modulo $998244353$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $n$, oznaczającą liczbę miast.

Druga linia zawiera $n$ liczb całkowitych, oznaczających wartości $a_i$.

Następne $n-1$ linii zawiera po dwie liczby całkowite $u, v$, oznaczające krawędź w drzewie.

Wyjście

Wyprowadź jedną liczbę całkowitą oznaczającą wynik.

Przykład

Przykład 1

Wejście:

2
1 2
1 2

Wyjście:

7

Uwagi

• Gdy $w_1=1$, zbiór $\{1\}$ jest harmonijny, co zdarza się z prawdopodobieństwem $\frac 12$.
• Gdy $w_2=1$, zbiór $\{2\}$ jest harmonijny, co zdarza się z prawdopodobieństwem $\frac 13$.
• Gdy $w_1=w_2=1$ lub $w_1=0,w_2=2$, zbiór $\{1,2\}$ jest harmonijny, co zdarza się z prawdopodobieństwem $\frac 13$.

Zatem oczekiwana liczba harmonijnych spójnych podzbiorów wynosi $\frac 12 + \frac 13 + \frac 13 = \frac 76$.

Przykład 2

Wejście:

3
2 1 3
1 2
1 3

Wyjście:

46

Ograniczenia

Dla $100\%$ danych wejściowych: $1\le n\le 3000$. Dla każdego $1\le i\le n$ zachodzi $1\le a_i\le n$. Podane krawędzie $u, v$ tworzą drzewo.

Dla testów $1\sim 3$: $n\le 50$.

Dla testów $4\sim 5$: $\sum a_i \le 5000$.

Dla testów $6\sim 7$: drzewo jest ścieżką, gdzie $v=u+1$.

Dla testu $8$: $a_i=n$.

Dla testów $9\sim 10$: brak dodatkowych ograniczeń.