题目背景

You are given a peach tree $T$.

You don't need to think of the peach.

Because I'm going to talk about the tree.

题目描述

冒泡排序算法是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $a[0], a[1], \dots, a[n-1]$ 从小到大排序的冒泡排序算法可以用下面的伪代码描述。

for (int i = 1; i <= k; i++)
    for (int j = 0; j < n-1; j++)
        if (a[j] > a[j+1]) {
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
        }

其中 $k$ 称为冒泡排序进行的轮数，当 $k$ 取 $n$ 时，便可以保证序列被从小到大排序。

序排泡冒算法是一种鲜为人知的序排算法，其作用是给定一个长度为 $n$ 的序列 $a$ 和参数 $k$，输出所有可能的序列 $b$，满足其经过 $k$ 轮冒泡排序之后成为序列 $a$。

给定一棵树 $T$，结点用 $1,2, \dots, n$ 编号。每一个结点 $u$ 有一个点权 $p(u)$，保证 $p(1), p(2), \dots, p(n)$ 构成了 $\{1,2,\dots,n\}$ 的一个排列。换言之，满足

1. 对于 $u\ne v$，均有 $p(u)\ne p(v)$；
2. 对于任意的 $i\in \{1, 2, \dots, n\}$，均存在一个 $u$ 满足 $p(u)=i$。

对于这棵树，我们将进行 $m$ 次询问，每次询问给出两个结点 $u, v$ 和一个参数 $k$。用 $t_1, t_2, \dots, t_l$ 表示从 $u$ 到 $v$ 的唯一简单路径上依次经过的所有结点的点权组成的序列，可以看出 $t_1$ 就是 $p(u)$，$t_l$ 就是 $p(v)$，你需要计算序列 $t$ 和参数 $k$ 进行序排泡冒后，输出的排列序列个数。换言之，求有多少个序列满足其经过 $k$ 轮冒泡排序后得到序列 $t$。

由于答案很大，你只需要输出其对 $998,244,353$ 取模的结果（也就是说，输出答案除以 $998,244,353$ 的余数）。

输入格式

第一行包含两个用空格分隔的自然数 $n, m$，表示结点个数和询问个数。

接下来的一行包含 $n$ 用空格分隔的整数 $p(1), p(2), \dots, p(n)$，表示每个点的点权。

接下来 $n-1$ 行每行包含两个数 $x_i, y_i$，表示树上存在一条连接 $x_i$ 和 $y_i$ 上的边。输入的数据保证所有的边构成一棵树。

接下来 $m$ 行每行包含一个询问 $u_i, v_i, k_i$，其意义在题目描述中已经说明。

输出格式

输出包含 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案对 $998,244,353$ 取模的结果。

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

1
2
0
4

见附件中的 2.in。

见附件中的 2.ans。

提示

【样例解释 #1】

在这组样例中，树构成了一个长度为 $4$ 的链。

1. 对于第一次询问，经过的结点序列为 $[1]$，点权序列为 $[1]$，序排泡冒输出 $\{[1]\}$。
2. 对于第二次询问，经过的结点序列为 $[1,2]$，点权序列为 $[1,3]$，序排泡冒输出 $\{[1,3], [3,1]\}$。
3. 对于第三次询问，经过的结点序列为 $[1,2,3]$，点权序列为 $[1,3,2]$，序排泡冒输出 $\{\}$。
4. 对于第四次询问，经过的结点序列为 $[1,2,3,4]$，点权序列为 $[1,3,2,4]$，序排泡冒输出 $\{[1,3,4,2], [3,1,4,2], [1,4,3,2], [4,1,3,2]\}$。

【子任务】

Subtask	$n$	$m$	$k$	Type	Score
$1$	$\le 5 \times 10^{5}$		$= 0$	$3$	$1$
$2$	$\le 10$	$\le 1$	$\le n$	$1$	$4$
$3$		$\le 5 \times 10^{5}$		$3$
$4$	$\le 10^{3}$			$1$	$10$
$5$	$\le 5 \times 10^{5}$				$12$
$6$				$2$	$13$
$7$	$\le 10^{3}$			$3$	$5$
$8$	$\le 10^{5}$				$25$
$9$	$\le 5 \times 10^{5}$				$27$

对于所有数据，$1\le n,m\le 5\times 10^5, 0\le k\le n$。

数据类型含义：

• $\mathrm{Type}=1$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_1=1, v_i=n$。
• $\mathrm{Type}=2$：树构成一条链，即 $x_i = i,y_i=i+1$，并且所有的询问都满足 $u_i < v_i$。
• $\mathrm{Type} = 3$：无特殊限制。

【提示】

Don't be afraid of the pain in climbing.

Your tough journey is just beginning.

But the fruit you will gain is not only peaches.

Keep counting on the tree! Young gentlemen and ladies.

Hope in your heart will lead you to the destiny.