Description

master is very interested in sums on trees. He generated a rooted tree and wants to query, multiple times, the sum of the $k$-th power of the depths of all nodes on a path, and $k$ may be different each time. Here, the depth of a node is defined as the number of edges on the path from this node to the root. He handed this problem to pupil, but pupil does not know how to perform such complex operations. Can you help him?

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

Each of the next $n - 1$ lines contains two space-separated positive integers $i, j$, indicating an edge between nodes $i$ and $j$ in the tree.

The next line contains a positive integer $m$, the number of queries.

Each of the next $m$ lines contains three space-separated positive integers $i, j, k$, representing a query asking for the sum of the $k$-th power of the depths of all nodes on the path from node $i$ to node $j$. Since the result can be very large, output it modulo $998244353$.

Nodes are numbered starting from $1$, and node $1$ is the root.

Output Format

For each query, output one line with a single integer, the result modulo $998244353$.

5
1 2
1 3
2 4
2 5
2
1 4 5
5 4 45

33
503245989

Hint

Sample Explanation

Let $d (i)$ denote the depth of node $i$.

For the sample tree, $d (1) = 0, d (2) = 1, d (3) = 1, d (4) = 2, d (5) = 2$.

Therefore, the answer to the first query is $(2^5 + 1^5 + 0^5) \bmod 998244353 = 33$; the answer to the second query is $(2^{45} + 1^{45} + 2^{45}) \bmod 998244353 = 503245989$.

Constraints

• For $30\%$ of the testdata, $1 \leq n, m \leq 100$.
• For $60\%$ of the testdata, $1 \leq n, m \leq 1000$.
• For $100\%$ of the testdata, $1 \leq n, m \leq 300000$, $1 \leq k \leq 50$.

Additionally, there are $5$ unscored hack testdata.

Tip

The input size is large; please use fast I/O.

Translated by ChatGPT 5