The Tree's Ballad

Under the shade of a great tree, recite an old verse and let your feelings flow. In this problem, you are given a rooted tree with n nodes numbered from 1 to n, where node 1 is the root. Each node has a depth (with the root having depth 1).

You are also given a constant k and Q queries. Each query consists of two integers x and y. For each query, consider all nodes i with 1 ≤ i ≤ x, compute the lowest common ancestor (LCA) of node i and y, and take the depth of that LCA raised to the power k. Formally, you are to compute:

Because the answer may be very large, output it modulo 998244353.

Notes:

• lca(u, v) denotes the lowest common ancestor of nodes u and v.
• depth(u) is the depth of node u with the root's depth being 1.

If you have solved many problems already, take a moment under this great tree to recite an old poem and enjoy the sentiment!

inputFormat

The first line contains three integers: n, Q, and k. The second line contains n-1 integers: p₂, p₃, …, pₙ, where pᵢ is the parent of node i (for 2 ≤ i ≤ n). Each of the next Q lines contains two integers x and y describing a query.

outputFormat

For each query, output the computed summation modulo 998244353 on a separate line.

sample

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

7
4
3