Source : 2019贵州省选Day2
Description

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

  温一壶风尘的酒
  独饮往事迢迢
  举杯轻思量
  泪如潮青丝留他方
  ——乌糟兽/愚青《旧词》
  你已经解决了五个问题,不妨在这大树之下,吟唱旧词一首抒怀。最后的问题就是关于这棵树的,它的描述很简单。
  给定一棵 nn 个点的有根树,节点标号 1 n1~n11 号节点为根。
  给定常数 kk
  给定 QQ 个询问,每次询问给定 x,yx,y
  求:
ixdepth(lca(i,y))k\sum_{i\leq x}depth(lca(i,y))^k
  lca(x,y)lca(x,y) 表示节点 xx 与节点 yy 在有根树上的最近公共祖先。
  depth(x)depth(x) 表示节点 xx 的深度,根节点的深度为 11
  由于答案可能很大,你只需要输出答案模 998244353998244353 的结果。

Input

  输入包含 n+Qn+Q 行。
  第 11 行,三个正整数 n,Q,kn,Q,k
  第 i=2 ni=2~n 行,每行有一个正整数 fai(1fain)fa_i(1 \leq fai\leq n),表示编号为 ii 的节点的父亲节点的编号。
  接下来 QQ 行,每行两个正整数 x,y(1x,yn)x,y(1 \leq x,y \leq n),表示一次询问。

Output

  输出包含 QQ 行,每行一个整数,表示答案模 998244353998244353 的结果。

Sample Input
5 5 2
1
4
1
2
4 3
5 4
2 5
1 2
3 2
Sample Output
15
11
5
1
6
Hint

样例说明
  输入的树:
  1
  | \
  2 4 - 3
  |
  5
  每个点的 depth 分别为 1, 2, 3, 2, 3。
  第一个询问 x=4,y=3x = 4, y = 3,容易求出:
  lca(1,3)=1lca(1, 3) = 1
  lca(2,3)=1lca(2, 3) = 1
  lca(3,3)=3lca(3, 3) = 3
  lca(4,3)=4lca(4, 3) = 4
  于是 depth(1)2+depth(1)2+depth(3)2+depth(4)2=1+1+9+4=15depth(1)^2+depth(1)^2+depth(3)^2+depth(4)^2 = 1+1+9+4 = 15