题目描述

冒泡排序算法是一种广为人知的排序算法，其思路在于不断地交换相邻且逆序的两个元素，由于总的逆序对个数不断减少，冒泡排序算法一定可以终止。给 $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$ 取模的结果。

输入输出样例 #1

输入 #1

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

1
2
0
4

说明/提示

【样例解释 #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]\}$。

【子任务】

对于所有数据，$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$：无特殊限制。