Migrated from Lutece 3191 意外伤害

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

白银武手受伤了。

被头发给割伤了……

处于和平年代的白银武不再与 BETA 斗争，但他仍然受伤了——被头发给割伤了，于是将以下问题抛给了你：

有一棵树，$n$ 个结点，编号为 $1 \sim n$，每个点有一个权值 $a_i$。这些点组成了一个全集 $T$。

你需要找到满足以下条件的点的集合 $S$ 数量：

• $S$ 是 $T$ 的非空子集
• 令 $G$ 是 $S$ 在 $T$ 中的导出子图，则 $G$ 形成了一棵树，且树的所有度数为 $1$ 的节点都拥有相同的权值。

由于数量可能很大，请你输出对 $998244353$ 取模的结果。

Input

第一行一个正整数 $n$，代表树的结点数量。

第二行 $n$ 个正整数，第 $i$ 个正整数代表结点编号为 $i$ 的结点的权值。

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$，代表树的一条边。

Output

一个整数，代表满足条件的点集数量对 $998244353$ 取模的结果。

Samples

3
1 2 1
1 2
2 3

4

Constraints

$1 \le n \le 3 \times 10^5$

$1 \le a_i \le n$

$1 \le u_i, v_i \le n$

Resources

2024 UESTC ICPC Training for Graph