Description

东条把想淋的巧克力做成了一个巧克力喷泉树。巧克力喷泉树是一棵 $n$ 个节点的树。每个节点都有一个西西弗水果。对于每一个节点 $u$，你有两种选择：你可以在节点 $u$ 放置 $a_u$ 个水果，也可以一个水果都不放。然后，东条会在根节点往下淋巧克力汁。节点 $u$ 给最原带来的营养值是 $u$ 及其子树中所放置的西西弗水果的数量。东条想要知道，对于所有 $2^n$ 个放水果方案，最原所获得的营养值之和的总和是多少。答案对 $998244353$ 取余。

树的根节点为 $1$。

Input Format

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

后面 $n-1$ 行每行两个正整数 $u,v$ $(1\le u,v\le n)$，代表有树中一条边 $(u,v)$。

Output Format

一行，一个整数代表答案。

3
1 1 2
1 2
2 3

36

Hint

样例 1 解释

用 $S$ 表示选中状态

• $S=000$ 贡献 $0$
• $S=001$ 贡献 $1$
• $S=010$ 贡献 $2$
• $S=011$ 贡献 $3$
• $S=100$ 贡献 $6$
• $S=101$ 贡献 $7$
• $S=110$ 贡献 $8$
• $S=111$ 贡献 $9$

数据规模与约定

对于 $20\%$ 的数据，满足 $n\le 20$。

对于另外 $30\%$ 的数据，满足 $u=v-1$。

对于 $100\%$ 的数据，满足 $2\le n\le 10^6$，$1 \le a_i \le 10^9$。