题目描述

小 F 的生日还有一个多月，大 F 早早地准备起了礼物。

“你想要什么礼物呀？嗯...要不要好吃的？”

“才不要呢，我想要好看的花，永远不会凋谢的花。”

小 F 和大 F 一起生活的国家—— Fairy 国，可以抽象成一棵 $N$ 个节点的树，每个节点就是一个城市，编号为 $1\ldots N$。

大 F 要游历各个城市，为心爱的小 F 寻找好看的花。

Fairy 国的每个城市都有一座山，山上有恰好一朵永远不会凋谢的花，编号为 $i$ 的城市的花的美丽值为 $B_i$。大 F 要在 $N$ 个城市中选出恰好 $M$ 个，并摘来这 $M$ 个城市中的 $M$ 朵花送给小 F。可是呢，如果树上的一条边连接的两个城市的花都被摘去，这条边就会塌陷，Fairy 国就会陷入分裂，大 F 作为一个善良的人，不希望这样的情况发生。所以，一种摘法合法，当且仅当对于每条边，这条边相连的两个节点的花不被同时摘去。

大 F 希望小 F 快乐，小 F 的快乐程度将是摘来的 $M$ 朵花的美丽程度的积。大 F 今天闲着没事，想要求出对于所有合法的摘法，小 F 的快乐程度之和对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $N$ 和 $M$，表示节点的个数与大 F 要为小 F 摘的花的朵数。

第二行 $N$ 个整数 $B_{1\ldots N}$，表示 $N$ 朵花的美丽程度。

接下来 $N-1$ 行，每行两个正整数，描述树上的一条边，保证形成一棵树。

输出格式

一个整数，表示对于所有合法的摘法，小 F 的快乐程度之和对 $998244353$ 取模的结果。

5 3
3 5 4 8 11
1 2
1 3
2 4
2 5

616

15 6
9 10 2 7 2 4 5 9 3 2 1 9 3 10 7
12 3
4 3
15 8
2 14
7 14
8 14
3 15
6 1
11 1
7 11
9 14
8 5
10 5
13 15

8214265

数据范围与提示

对于所有数据，保证 $1 \le M \le N \le 8 \times 10^4$，$0 \le B_i < 998244353$。

下表为各个 Subtask 的额外限制与得分，空格表示该项无额外限制。你只有通过一个 Subtask 的所有数据才能得到该 Subtask 的分。