Description

骗分过样例，暴力出奇迹。

关于树的算法有一大堆，样样都是毒瘤。

比如说 NOIP2018 提高组的 D2T3，如果会动态 DP 的做法那么就马上想到正解，但是 Tweetuzki 不会动态 DP，就只好骗分了。

可惜树题的码量也是超级大的。听说好多学长都会动态 DP，但是考场上调不出来，只好暴力分收场了。疯狂暗示

Tweetuzki 当时暴力写挂了，有 4 个点写成了死循环……于是分数白白少了 16 分。Tweetuzki 一想起这事，不禁夙夜忧叹，辗转反侧。

现在他又遇到一道毒瘤树上问题了，他下定决心：这次一定要把暴力分写满！

题目是这样的：

有一棵 $n$ 个点的树，边有边权，每个点有颜色 $c_i$。求所有颜色不同的点对的距离之和。由于答案可能很大，你只需要输出其对 $998,244,353$ 取模的结果即可。

形式化地讲，记 $u$ 号点和 $v$ 号点在树上的距离为 $\text{dist}(u, v)$，求：

$$\Large \left(\sum_{u = 1}^n \sum_{v = 1}^n [c_u \ne c_v] \text{dist}(u, v)\right) \bmod 998,244,353 $$

Input Format

从文件 count.in 中读入。

输入文件将会遵循以下格式：

$n \quad \text{type}$
$c_1 \quad c_2 \quad \cdots \quad c_n$
$u_1 \quad v_1 \quad w_1$
$u_2 \quad v_2 \quad w_2$
$\vdots$
$u_{n - 1} \quad v_{n - 1} \quad w_{n - 1}$

第一行两个正整数 $n, \text{type}$ $(2 \le n \le 2 \times 10^5, 1 \le \text{type} \le 6)$，其中 $n$ 表示点数，$\text{type}$ 为部分分类型，详见数据范围，$\text{type} = 0$ 表示样例数据。
第二行输入 $n$ 个正整数 $c_i$ $(1 \le c_i \le 10^9)$，表示每个点的颜色。
接下来 $n - 1$ 行，每行输入三个正整数 $u_i, v_i, w_i$ $(1 \le u_i < v_i \le n, 1 \le w_i \le 10^9)$，描述这棵树。

Output Format

输出到文件 count.out 中。

输出一行一个非负整数，表示答案对 $998, 244, 353$ 取模的结果。

Sample

样例输入 1

4 0
1 2 3 3
1 2 5
2 3 4
3 4 7

样例输出 1

90

样例解释 1

满足条件的点对有 $(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1), (4, 2)$，故答案为 $5 + 9 + 16 + 5 + 4 + 11 + 9 + 4 + 16 + 11 = 90$。

样例输入 2

8 0
2 3 5 1 2 3 4 1
1 2 12345
1 3 234567
1 5 3456
2 4 4567890
2 6 567
3 7 67
4 8 7

样例输出 2

115703306

Hint

Subtask #1 (20 points)：$n \le 300$, $\text{type} = 1$。
Subtask #2 (20 points)：$n \le 2\ 000$, $\text{type} \le 2$。
Subtask #3 (10 points)：$n \le 10\ 000$, $\text{type} \le 3$。
Subtask #4 (20 points)：对于第 $i$ $(1 \le i \le n)$ 号点，$c_i = i$。$\text{type} = 4$。
Subtask #5 (20 points)：对于第 $i$ $(1 \le i < n)$ 条边，$u_i + 1 = v_i$。$\text{type} = 5$。
Subtask #6 (10 points)：无特殊性质，$\text{type} \le 6$。

提示：对于提高组选手而言，本题满分可视作 90 分。