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$，没有特殊限制。