给定一棵包含 $N$ 个顶点和 $N-1$ 条边的树 $T$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边 ($1 \le i \le N-1$) 连接顶点 $U_i$ 和 $V_i$。此外，每个顶点 $v$ ($1 \le v \le N$) 上写有一个整数 $A_v$。

选择树中部分边的方案共有 $2^{N-1}$ 种。对于每种选择，得分定义如下：

• 令 $G$ 为从 $T$ 中移除未被选择的边后得到的图。对于 $G$ 的每个连通分量，考虑其顶点上所写整数的最小值，并将这些最小值求和。该和即为得分。

求所有选择方案的得分之和，对 $998244353$ 取模。

输入格式

输入通过标准输入按以下格式给出：

$N$ $A_1$ $A_2$ $\dots$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_{N-1}$ $V_{N-1}$

• 输入中的所有值均为整数。
• $2 \le N \le 3 \times 10^5$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le U_i, V_i \le N$ ($1 \le i \le N-1$)
• 给定的图是一棵树。

输出格式

输出答案。

样例

样例输入 1

4
1 2 3 4
1 2
2 4
3 2

样例输出 1

44

样例输入 2

5
3 5 6 5 1
4 1
2 3
3 5
1 3

样例输出 2

154