Description

Bob likes segment trees.

As everyone knows, the second problem of ZJOI contains many segment trees.

Bob has a generalized segment tree whose root is $[1, n]$. Bob needs to perform $k$ range lazy-tag operations on this segment tree. Each operation uniformly at random selects one sub-interval from all $\dfrac{n(n+1)}{2}$ sub-intervals of $[1, n]$. For every non-leaf node visited during this operation, Bob will push down the tag on this node; for every leaf node (i.e. a node where the recursion does not continue), Bob will set a tag on this node.

Bob wants to know: after $k$ operations, what is the expected number of nodes that have a tag.

【Precise definitions】

Segment tree: A segment tree is a binary tree where each node stores a segment. The root node stores the segment $[1, n]$. For each node, if it stores $[l, r]$ and $l \neq r$, let $m = \lfloor \dfrac{l+r}{2} \rfloor$, then its left and right children store $[l, m]$ and $[m + 1, r]$ respectively; if $l = r$, then it is a leaf node.

Generalized segment tree: In a generalized segment tree, $m$ is not required to be exactly the midpoint of the interval, but it must still satisfy $l \leq m < r$. It is not hard to see that in a generalized segment tree, the depth of the tree can reach $O(n)$.

The core of a segment tree is lazy tags. Below is pseudocode for a generalized segment tree with lazy tags, where the tag array represents lazy tags:

Note that when processing a leaf node, once it gets a tag, this tag will remain forever.

You can also understand the problem as follows: There is a generalized segment tree, and each node has an $m$ value. Initially, all values in the tag array are $0$. Bob will perform $k$ operations. Each operation uniformly at random selects an interval $[l, r]$ and executes MODIFY(root,1,n,l,r);. In the end, the expected number of all Node such that tag[Node]=1 is the value you need to compute.

Input Format

The first line contains two integers $n, k$.

The next line contains $n - 1$ integers $a_i$: in preorder traversal order, they give the split position $m$ of every non-leaf node in the generalized segment tree. You can also understand it like this: starting from a tree with only the root node $[1, n]$, each time you read an integer, you split the current node whose interval contains this integer once, and finally you obtain a generalized segment tree with $2n - 1$ nodes.

It is guaranteed that the given $n - 1$ integers form a permutation. It is not hard to see that with this information, a unique generalized segment tree on $[1, n]$ can be determined.

Output Format

Output one integer, representing the expected value modulo $p = 998244353$. That is, if the expected value in lowest terms is $\dfrac{a}{b}$, you need to output an integer $c$ such that $c \times b \equiv a \pmod p$.

3 1
1 2

166374060

5 4
2 1 3 4

320443836

Hint

The sample input/output for $3$ is provided in the attachment.

Sample explanation $1$

The input segment tree is $[1, 3], [1, 1], [2, 3], [2, 2], [3, 3]$.

If the operation is $[1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3]$, the number of tagged nodes is $1$. If the operation is $[1, 2]$, the number of tagged nodes is $2$. Therefore, the answer is $\dfrac{7}{6}$.

For $100\%$ of the data, $1 \leq n \leq 200000, 1 \leq k \leq 10^9$.

Translated by ChatGPT 5