Color (color, 3s, 512M)

Bytejump 近期推出了一款新玩具：Bytecolor。在这个玩具中，玩家需要给 Bytecity 上色。

Bytecity 的结构可以由一棵树描述：有 $n-1$ 条双向道路连接所有城市。调色板中有 $k$ 种颜色，一开始某些城市已经上好色了（也是 $k$ 种颜色中的），玩家需要用调色板中的颜色给剩余的每个城市上色（颜色可以重复），且相邻城市不能同色。

你想要知道玩家一共能得到多少种可能的树（即有多少种不同的染色方案），对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,k$，表示城市数和颜色数。

接下来 $n$ 行，第 $i$ 行一个非负整数 $c_i \in [0,k]$，表示城市 $i$ 的开始颜色，0表示尚未上色，否则表示已经上好的颜色编号。

最后 $n-1$ 行描述树边。第 $i$ 行两个正整数 $u_i,v_i$，表示第 $i$ 条树边连接的两个城市。

输出格式

输出一行一个 $[0,998244352]$ 的整数，表示玩家一共能得到多少种可能的树对 $998244353$ 取模。

样例输入1

4 3
1 0 0 2
1 2
2 3
3 4

样例输出1

3

有 1212, 1232, 1312 三种上色方案。

样例输入2、样例输出2

见选手文件夹下 ex_color2.in 和 ex_color2.ans。

样例输入3、样例输出3

见选手文件夹下 ex_color3.in 和 ex_color3.ans。

数据范围

对于所有数据，$1\le n\le 10^5$，$1\le k\le 10^9$，$0\le c_i\le k$。

对于 10% 的数据，$n,k\le 9$。

对于 20% 的数据，$n,k\le 50$。

对于 40% 的数据，$n,k\le 1000$。

对于 60% 的数据，$n \le 1000$。

对于另外 20% 的数据，$k\le 10^5$。