#3312. 「ZJOI2020」传统艺能

题目描述

Bob 喜欢线段树。

众所周知，ZJOI 的第二题有很多线段树。

Bob 有一棵根为 $[1, n]$ 的广义线段树。Bob 需要在这个线段树上执行 $k$ 次区间懒标记操作，每次操作会等概率地从 $[1, n]$ 的所有 $\frac{n(n+1)}{2}$ 个子区间中随机选择一个。对于所有在该次操作中被访问到的非叶子节点，Bob 会将这个点上的标记下推；而对于所有叶子节点（即没有继续递归的节点），Bob 会给这个点打上标记。

Bob 想知道，$k$ 次操作之后，有标记的节点的期望数量是多少。

具体定义

线段树：线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。

对于每个节点，若它记录的线段是 $[l, r]$ 且 $l \neq r$，取 $m = \lfloor \frac{l+r}{2} \rfloor$，则它的左右儿子节点记录的线段分别是 $[l, m]$ 和 $[m + 1, r]$；若 $l = r$，则它是叶子节点。

广义线段树：在广义的线段树中，$m$ 不要求恰好等于区间的中点，但是 $m$ 还是必须满足 $l \le m < r$ 的。不难发现在广义的线段树中，树的深度可以达到 $O(n)$ 级别。

注意，在处理叶子节点时，一旦它获得了一个标记，那么这个标记会一直存在。

---

输入格式

第一行输入两个整数 $n, k$。

接下来输入一行包含 $n - 1$ 个整数 $a_i$：按照先序遍历的顺序，给出广义线段树上所有非叶子节点的划分位置 $m$。你也可以理解为从只有 $[1, n]$ 根节点开始，每次读入一个整数后，就将当前包含这个整数的节点做一次拆分，最后获得一棵有 $2n - 1$ 个节点的广义线段树。

保证给定的 $n - 1$ 个整数是一个排列，不难发现通过这些信息就能唯一确定一棵 $[1, n]$ 上的广义线段树。

---

输出格式

输出一行一个整数，代表期望数量对 $p = 998244353$ 取模后的结果。即，如果期望数量的最简分数表示为 $\frac{a}{b}$，你需要输出一个整数 $c$ 满足 $c \times b \equiv a \pmod{p}$。

---

样例 1

输入

3 1
1 2

输出

166374060

解释 输入的线段树为 $[1, 3], [1, 1], [2, 3], [2, 2], [3, 3]$。

若操作为 $[1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3]$，标记个数为 $1$。若操作为 $[1, 2]$，标记个数为 $2$。故答案为 $\frac{7}{6}$。

---

样例 2

输入

5 4
2 1 3 4

输出

320443836

---

数据范围与提示

测试点	$n$	$k$	其他约定
1	$\le 10$	$\le 4$
2	$\le 100$
3		$\le 5$
4		$=1$
5	$=32$		输入的线段树为完全二叉树
6	$=64$
7	$=4096$
8	$\le 5000$		每个 $m$ 均在 $[l, r-1]$ 内均匀随机
9	$\le 100000$
10

对于 $100\%$ 的数据，$1 \le n \le 200000, 1 \le k \le 10^9$。

---