Floating life has three thousand dreams, Exhausting thousands of miles of poetry and wine in desolation. In vain pouring out one's ideals, It is better to return home early.

Warm a pot of worldly wine, Drinking alone of the distant past. Raising a cup to ponder lightly, Tears like a tide, black hair left in another land.

— Wu Zao Shou / Yu Qing, "Old Words"

You have already solved five problems; why not sing a song of "Old Words" under this great tree to express your feelings? The final problem is about this tree, and its description is very simple.

Given a rooted tree with $n$ nodes, labeled $1 \sim n$, where node $1$ is the root. Given a constant $k$. Given $Q$ queries, each query provides $x, y$. Calculate: $$\sum_{i \le x} depth(lca(i, y))^k$$

$lca(x, y)$ denotes the lowest common ancestor of node $x$ and node $y$ in the rooted tree. $depth(x)$ denotes the depth of node $x$, where the depth of the root is $1$. Since the answer can be very large, you only need to output the result modulo $998244353$.

Input

The input contains $n + Q$ lines. The first line contains three positive integers $n, Q, k$. For the $i = 2 \sim n$-th lines, each line contains a positive integer $fa_i$ ($1 \le fa_i \le n$), representing the parent of node $i$. The next $Q$ lines each contain two positive integers $x, y$ ($1 \le x, y \le n$), representing a query.

Output

The output contains $Q$ lines, each containing an integer representing the result modulo $998244353$.

Examples

Input 1

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

Output 1

15
11
5
1
6

Note

The input tree:

1
| \
2 4 - 3
|
5

The depths of the nodes are $1, 2, 3, 2, 3$ respectively. For the first query $x = 4, y = 3$, it is easy to find: $lca(1, 3) = 1$ $lca(2, 3) = 1$ $lca(3, 3) = 3$ $lca(4, 3) = 4$ Thus $depth(1)^2 + depth(1)^2 + depth(3)^2 + depth(4)^2 = 1 + 1 + 9 + 4 = 15$.

Data Scale and Convention