A85877.「GXOI / GZOI2019」旧词

浮生有梦三千场
穷尽千里诗酒荒
徒把理想倾倒
不如早还乡

温一壶风尘的酒
独饮往事迢迢
举杯轻思量
泪如潮青丝留他方

——乌糟兽/愚青《旧词》

你已经解决了五个问题，不妨在这大树之下，吟唱旧词一首抒怀。最后的问题就是关于这棵树的，它的描述很简单。

给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。
给定常数 $k$。
给定 $Q$ 个询问，每次询问给定 $x,y$。
求：

$$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$

$\text{lca}(x,y)$ 表示节点 $x$ 与节点 $y$ 在有根树上的最近公共祖先。
$\text{depth}(x)$ 表示节点 $x$ 的深度，根节点的深度为 $1$。
由于答案可能很大，你只需要输出答案模 $998244353$ 的结果。

输入包含 $n+Q$ 行。
第 $1$ 行，三个正整数 $n,Q,k$。
第 $i = 2 \sim n$ 行，每行有一个正整数 $f_i(1 \le f_i \le n)$，表示编号为 $i$ 的节点的父亲节点的编号。
接下来 $Q$ 行，每行两个正整数 $x,y(1 \le x,y \le n)$，表示一次询问。

输出包含 $Q$ 行，每行一个整数，表示答案模 $998244353$ 的结果。

测试点编号	$n$ 的规模	$Q$ 的规模	$k$ 的规模	约定
$1$	$n \le 2,000$	$Q \le 2,000$	$1 \le k \le 10^9$	无
$2$	$n \le 2,000$	$Q \le 2,000$	$1 \le k \le 10^9$	无
$3$	$n \le 2,000$	$Q \le 2,000$	$1 \le k \le 10^9$	无
$4$	$n \le 2,000$	$Q \le 2,000$	$1 \le k \le 10^9$	无
$5$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	存在某个点，其深度为 $n$
$6$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	存在某个点，其深度为 $n$
$7$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	存在某个点，其深度为 $n$
$8$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	存在某个点，其深度为 $n$
$9$	$n \le 50,000$	$Q = n$	$1 \le k \le 10^9$	对于第 $i$ 个询问，有 $x = i$
$10$	$n \le 50,000$	$Q = n$	$1 \le k \le 10^9$	对于第 $i$ 个询问，有 $x = i$
$11$	$n \le 50,000$	$Q \le 50,000$	$k = 1$	无
$12$	$n \le 50,000$	$Q \le 50,000$	$k = 1$	无
$13$	$n \le 50,000$	$Q \le 50,000$	$k = 2$	无
$14$	$n \le 50,000$	$Q \le 50,000$	$k = 2$	无
$15$	$n \le 50,000$	$Q \le 50,000$	$k = 3$	无
$16$	$n \le 50,000$	$Q \le 50,000$	$k = 3$	无
$17$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	无
$18$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	无
$19$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	无
$20$	$n \le 50,000$	$Q \le 50,000$	$1 \le k \le 10^9$	无