Bubble Sort Reversal on Trees

In this problem, we introduce a little‐known algorithm called the Sequence Bubble Sort Reversal algorithm. Recall that the standard bubble sort algorithm (which we describe in pseudocode below) sorts an array a = [a_0, a_1, ..., a_{n-1}] in ascending order by repeatedly swapping adjacent elements that are in the wrong order. For example, the following pseudocode performs k rounds of bubble sort:

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

When k = n, the sequence is guaranteed to be sorted in increasing order. The Sequence Bubble Sort Reversal algorithm is defined as follows: given a sequence a (of length n) and an integer parameter k, enumerate all sequences b that are permutations of a such that after performing k rounds of bubble sort on b the resulting sequence equals a.

We now combine this idea with a tree problem. You are given a tree T with n nodes numbered 1,2,...,n. Each node u has an associated weight p(u), and the weights form a permutation of {1, 2, …, n}. That is, for every i from 1 to n there is exactly one node with weight i.

There are m queries. In each query you are given two nodes u and v and an integer parameter k. Let t = [t_1, t_2, ..., t_l] be the sequence of weights on the unique simple path from u to v (in order, so that t_1 = p(u) and t_l = p(v)). Your task is to compute the number of sequences b (which are permutations of t) that, after performing k rounds of bubble sort, result in the sequence t.

Observation. Because bubble sort only swaps adjacent elements and an element can move at most one position to the left per round, if an element ends at final position i (0-indexed) then in the original permutation it could have been at any position r satisfying
\( r - i \le k \) (with no restriction on how far right it slides). It turns out that if you label the final positions from 0 to l-1, the necessary and sufficient condition for a permutation p (where p(i) is the original index of the element that ends at final position i) is that

\( p(i) \le i + k \) for all \( 0 \le i \le l-1 \).

An easy combinatorial argument shows that the total number of valid original sequences b is given by:

\( \displaystyle \text{ans} = \begin{cases} l! & \text{if } k \ge l-1,\\[1mm] (k+1)^{l-k} \times k! & \text{if } k < l-1. \end{cases} \mod 998\,244\,353.

Here, l is the length of the path (i.e. the number of nodes encountered) from u to v in the tree. Your program needs to answer all m queries.

Input Constraints: You may assume that the input is such that the tree is connected and the node weights form a permutation of {1,2,...,n}. Also, k is a non-negative integer.

Input Format

• The first line contains two integers n and m.
• The second line contains n integers: p(1), p(2), ..., p(n).
• The next n-1 lines each contain two integers u and v, indicating an edge in the tree.
• The following m lines each contain three integers: u v k, representing a query.

Output Format

• For each query, output a single integer: the number of sequences b that produce the given sequence t after k rounds of bubble sort, modulo 998244353.

inputFormat

The input begins with a line containing two integers n (the number of nodes) and m (the number of queries). The second line contains n distinct integers p(1), p(2), ..., p(n) – a permutation of 1, 2, ..., n. Each of the next n-1 lines contains two integers u and v representing an edge in the tree. Then, there are m lines; each line contains three integers u, v, k, where u and v are nodes in the tree and k is the number of rounds of bubble sort.

outputFormat

For each query, print the result (the number of valid sequences b modulo 998244353) on a separate line.

sample

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

4
1
2

</p>