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\}$ 是和谐的，这有 $\frac13$ 的概率发生。

因此，总共期望有 $\frac12 + \frac13 + \frac13=\frac76$ 个和谐的连通块。

样例 2 输入

3
2 1 3
1 2
1 3

样例 2 输出

46

数据范围

对于 $100\%$ 的数据，保证 $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$，没有特殊限制。