给你一棵含有 $n$ 个节点的带色树，节点 $i$ 的颜色为 $c_i$。提示：一棵含有 $n$ 个节点的树是一个拥有 $n - 1$ 条边的连通图。

计算该树的连通子图数量，满足对于该子图，存在某种颜色（主导颜色），使得该子图中严格超过一半的节点都具有这种颜色。

由于答案可能非常大，请输出其对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3000$) — 树中节点的数量。

第二行包含 $n$ 个整数 $c_1\ c_2\ \dots\ c_n$ ($1 \le c_i \le n$) — 节点的颜色。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i$)，表示树的一条边 $(u_i, v_i)$。保证给定的图是一棵树。

输出格式

输出一个整数 — 问题的答案模 $998\,244\,353$ 的值。

样例

输入样例 1

3
2 3 3
1 2
2 3

输出样例 1

5

输入样例 2

4
1 1 3 3
1 2
1 3
1 4

输出样例 2

8

说明

在以下图片中，我们用蓝色代表颜色 1，红色代表颜色 2，黄色代表颜色 3。第一个样例的结构如下：

该树共有 6 个非空连通子图：3 个大小为 1，2 个大小为 2，1 个大小为 3（后者实际上是整棵树）。所有大小为 1 和 3 的子图都存在主导颜色。对于大小为 2 的子图，只有由顶点 1 和 2 导出的子图没有主导颜色（红色和黄色在其中出现的次数相同）。因此，共有 $6 - 1 = 5$ 个具有主导颜色的连通子图。

第二个样例的结构如下，它有 8 个具有主导颜色的连通子图：