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

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

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

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

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