Fytelandian 的科学家们以热爱历史研究而闻名。最近，他们发现了 $n$ 座城市遗迹，这些城市无疑属于一个伟大的古代文明。

所有被发现的城市由恰好 $n-1$ 条道路连接，且任意两座城市之间有且仅有一条路径。科学家在每座城市中都发现了大量文献，并得出结论：该文明的人民使用 $k$ 种不同的语言。在城市 $v$ 中，人们使用语言 $a_v$。

已知这些城市组成了若干个联盟，且每座城市恰好属于一个联盟。然而，联盟的具体构成尚不清楚。

设一个联盟为任意城市集合 $c_1, c_2, \dots, c_m$，它们之间可能通过道路连接，也可能不连接。为了管理该联盟，必须能够建立起不同城市之间使用不同语言的人员之间的联系。联盟的首领必须支持所有在城市 $c_i$ 中使用的语言，或者在联盟中任意两座城市 $c_i$ 和 $c_j$ 之间的最短路径上所使用的语言。

联盟中支持的语言越多，翻译官的工作就越困难——优秀的翻译官必须精通所有这些语言！幸运的是，许多语言彼此相似，翻译官掌握的语言越多，学习一门新语言就越容易。每多掌握一门新语言，翻译官学习下一门新语言所需的时间就会减半。

设联盟的语言难度为翻译官学习该联盟支持的所有语言所需的时间。第一门语言的学习时间为 $2^k$ 个单位，因此，若联盟支持的语言数量为 $t$，则该联盟的语言难度等于 $2^k + 2^{k-1} + \dots + 2^{k+1-t}$。注意，由于总共有 $k$ 种语言，该和始终为整数。

设联盟划分是将所有城市划分为若干个联盟的一种方案。如果两个联盟划分中存在两座城市 $u$ 和 $v$，它们在一个划分中属于同一个联盟，而在另一个划分中属于不同的联盟，则这两个联盟划分被认为是不同的。

设联盟划分的合理性为该划分中所有联盟的语言难度之和。

你需要计算所有可能的联盟划分的合理性之和。由于这个数字可能非常大，你只需要求出其对 $998\,244\,353$ 取模后的余数。

输入格式

第一行包含两个整数 $n$ 和 $k$ —— 分别表示城市数量和语言数量 ($1 \le n \le 5000; 1 \le k \le 10$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示各城市使用的语言 ($1 \le a_i \le k$)。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ —— 表示第 $i$ 条道路连接的城市 ($1 \le u_i, v_i \le n$)。

输出格式

输出所有可能的联盟划分的合理性之和，对 $998\,244\,353$ 取模。

样例

样例输入 1

3 2
1 2 1
1 2
2 3

样例输出 1

48

样例输入 2

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

样例输出 2

14504

说明

在第一个样例中，有三座城市。考虑所有可能的联盟划分：

• 三个联盟：

  • $\{1\}$。一座城市，唯一支持的语言是语言 1。语言难度为 $2^2 = 4$。
  • $\{2\}$。一座城市，唯一支持的语言是语言 2。语言难度为 $2^2 = 4$。
  • $\{3\}$。一座城市，唯一支持的语言是语言 1。语言难度为 $2^2 = 4$。 该划分的合理性为 $4 + 4 + 4 = 12$。

• 两个联盟：

  • $\{1, 2\}$。两座城市，支持语言 1 和 2。语言难度为 $2^2 + 2^1 = 6$。
  • $\{3\}$。一座城市，唯一支持的语言是语言 1。语言难度为 $2^2 = 4$。 该划分的合理性为 $6 + 4 = 10$。

• 两个联盟：

  • $\{1, 3\}$。两座城市，支持语言 1 和 2。注意，即使联盟中城市仅使用语言 1，语言 2 也会被支持，因为位于城市 1 和 3 之间最短路径上的城市 2 使用了语言 2。语言难度为 $2^2 + 2^1 = 6$。
  • $\{2\}$。一座城市，唯一支持的语言是语言 2。语言难度为 $2^2 = 4$。 该划分的合理性为 $6 + 4 = 10$。

• 两个联盟：

  • $\{1\}$。一座城市，唯一支持的语言是语言 1。语言难度为 $2^2 = 4$。
  • $\{2, 3\}$。两座城市，支持语言 1 和 2。语言难度为 $2^2 + 2^1 = 6$。 该划分的合理性为 $4 + 6 = 10$。

• 一个联盟：

  • $\{1, 2, 3\}$。三座城市，支持语言 1 和 2。语言难度为 $2^2 + 2^1 = 6$。 该划分的合理性为 $6$。

所求总和为 $12 + 10 + 10 + 10 + 6 = 48$。