题目描述

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

所有城市之间由恰好 $n-1$ 条道路连接，并且任意两座城市之间都恰好存在一条道路路径，因此这些城市和道路构成一棵树。

科学家在每座城市中发现了大量文字资料，并得知这个文明一共使用 $k$ 种不同的语言。在城市 $v$ 中，人们使用语言 $a_v$。

已知这些城市曾经组成若干个联盟，并且每座城市恰好属于一个联盟，但联盟的具体划分已经无法考证。

一个联盟可以是任意城市集合

它不一定在道路上连通。

为了管理联盟，需要能够在联盟内不同城市之间建立联系。因此，联盟负责人必须掌握所有满足下列条件之一的语言：

• 该语言在联盟中的某座城市 $c_i$ 使用；
• 该语言在某两座联盟城市 $c_i,c_j$ 之间的最短路径上的某座城市中使用。

设一个联盟需要支持的不同语言数量为 $t$。翻译者学习第一门语言需要 $2^k$ 个时间单位，之后每多学习一门语言，所需时间减半。因此该联盟的语言难度定义为

由于总共只有 $k$ 种语言，这个值一定是整数。

一个联盟划分是把所有城市划分成若干个互不相交的联盟。若存在两座城市 $u,v$，它们在一个划分中属于同一联盟，而在另一个划分中属于不同联盟，则这两个划分不同。

一个联盟划分的可信度定义为其中所有联盟的语言难度之和。

请计算所有可能联盟划分的可信度总和，并对

取模。

输入格式

第一行输入两个整数 $n,k$，分别表示城市数量和语言数量：

第二行输入 $n$ 个整数

其中

接下来 $n-1$ 行，每行输入两个整数 $u_i,v_i$，表示城市 $u_i$ 与 $v_i$ 之间有一条道路。

输出格式

输出所有可能联盟划分的可信度总和，对 $998244353$ 取模后的结果。

样例

样例 1

3 2
1 2 1
1 2
2 3

48

样例 2

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

14504