Problem Background

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.

Problem Description

Bubble Sort Algorithm is a well-known sorting algorithm that involves repeatedly swapping adjacent elements that are out of order. Since the total number of inversions decreases, the bubble sort algorithm is guaranteed to terminate. The bubble sort algorithm to sort $a[0], a[1], \dots, a[n-1]$ in ascending order can be described by the following pseudocode:

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;
        }

Here, $k$ is the number of rounds of bubble sort. When $k$ is set to $n$, it ensures that the sequence is sorted in ascending order.

Sequence Sort and Bubble Sort Algorithm is a lesser-known sorting algorithm that, given a sequence of length $n$ and a parameter $k$, outputs all possible sequences $b$ that become sequence $a$ after $k$ rounds of bubble sort.

Given a tree $T$ with nodes numbered $1, 2, \dots, n$. Each node $u$ has a point weight $p(u)$, and it is guaranteed that $p(1), p(2), \dots, p(n)$ form a permutation of $\{1, 2, \dots, n\}$. That is, it satisfies:

1. For $u \ne v$, $p(u) \ne p(v)$;
2. For any $i \in \{1, 2, \dots, n\}$, there exists a $u$ such that $p(u) = i$.

For this tree, we will perform $m$ queries. Each query provides two nodes $u, v$ and a parameter $k$. Let $t_1, t_2, \dots, t_l$ denote the sequence of point weights of all nodes on the unique simple path from $u$ to $v$, where $t_1$ is $p(u)$ and $t_l$ is $p(v)$. You need to calculate the number of sequences that, after $k$ rounds of bubble sort, result in sequence $t$. In other words, find how many sequences satisfy that they become sequence $t$ after $k$ rounds of bubble sort.

Since the answer can be very large, you only need to output the result modulo $998,244,353$ (i.e., the remainder when the answer is divided by $998,244,353$).

Input Format

The first line contains two space-separated natural numbers $n, m$, representing the number of nodes and the number of queries, respectively.

The next line contains $n$ space-separated integers $p(1), p(2), \dots, p(n)$, representing the point weights of each node.

The following $n-1$ lines each contain two numbers $x_i, y_i$, indicating an edge connecting nodes $x_i$ and $y_i$ in the tree. The input guarantees that all edges form a tree.

The next $m$ lines each contain a query $u_i, v_i, k_i$, as described in the problem statement.

Output Format

The output contains $m$ lines. The $i$-th line contains an integer representing the result of the $i$-th query modulo $998,244,353$.

Sample Input and Output

Sample Input #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

Sample Output #1

1
2
0
4

Sample Input #2

See attached file 2.in.

Sample Output #2

See attached file 2.ans.

Notes/Hints

[Sample Explanation #1]

In this sample, the tree forms a chain of length 4.

1. For the first query, the sequence of nodes is $[1]$, the point weight sequence is $[1]$, and the sequence sort and bubble sort output $\{[1]\}$.
2. For the second query, the sequence of nodes is $[1, 2]$, the point weight sequence is $[1, 3]$, and the sequence sort and bubble sort output $\{[1, 3], [3, 1]\}$.
3. For the third query, the sequence of nodes is $[1, 2, 3]$, the point weight sequence is $[1, 3, 2]$, and the sequence sort and bubble sort output $\{\}$.
4. For the fourth query, the sequence of nodes is $[1, 2, 3, 4]$, the point weight sequence is $[1, 3, 2, 4]$, and the sequence sort and bubble sort output $\{[1, 3, 4, 2], [3, 1, 4, 2], [1, 4, 3, 2], [4, 1, 3, 2]\}$.

[Subtasks]

For all data, $1 \le n, m \le 5 \times 10^5, 0 \le k \le n$.

Data Type Meanings:

• $\mathrm{Type}=1$: The tree forms a chain, i.e., $x_i = i, y_i = i+1$, and all queries satisfy $u_1 = 1, v_i = n$.
• $\mathrm{Type}=2$: The tree forms a chain, i.e., $x_i = i, y_i = i+1$, and all queries satisfy $u_i < v_i$.
• $\mathrm{Type}=3$: No special restrictions.

[Hints]

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.

见题面 Input 部分

见题面 Output 部分