Bob loves segment trees. As everyone knows, the second problem of ZJOI involves many segment trees.

Bob has a generalized segment tree rooted at $[1, n]$. Bob needs to perform $k$ range lazy-tag operations on this segment tree. In each operation, he chooses one of the $\frac{n(n+1)}{2}$ sub-intervals uniformly at random. For all non-leaf nodes visited during the operation, Bob pushes down the tag on that node; for all leaf nodes (i.e., nodes that do not continue to recurse), Bob applies a tag to that node.

Bob wants to know the expected number of nodes with tags after $k$ operations.

Definitions

Segment Tree: A segment tree is a binary tree where each node records a segment. The root node records the segment $[1, n]$. For each node, if it records the segment $[l, r]$ and $l \neq r$, let $m = \lfloor \frac{l+r}{2} \rfloor$; then its left and right child nodes record the segments $[l, m]$ and $[m + 1, r]$ respectively. If $l = r$, 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 $m$ must still satisfy $l \leq m < r$. It is not difficult to see that in a generalized segment tree, the depth of the tree can reach $O(n)$.

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

1: function Pushdown(Node)
2: if tag[Node]= 1 then
3: tag[Lson(Node)]← 1
4: tag[Rson(Node)]← 1
5: tag[Node]← 0
6: end if
7: end function
8:
9: function Modify(Node, l, r, ql, qr)
10: if [l, r] ∩ [ql, qr] = ∅ then
11: return
12: end if
13: if [l, r] ⊆ [ql, qr] then
14: tag[Node] ← 1
15: return
16: end if
17: m ← GetM(Node)
18: Pushdown(Node)
19: Modify(Lson(Node),l, m, ql, qr)
20: Modify(Rson(Node),m + 1, r, ql, qr)
21: end function

Note that when processing a leaf node, once it receives a tag, that tag will persist.

You can also understand the problem this way: there is a generalized segment tree, and each node has an $m$ value. Initially, all tag array values are $0$. Bob performs $k$ operations. In each operation, he chooses an interval $[l, r]$ uniformly at random and executes Modify(root, 1, n, l, r). The value to be calculated is the expected number of nodes such that tag[Node] = 1 at the end.

Input

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

The next line contains $n - 1$ integers $a_i$: these give the split positions $m$ for all non-leaf nodes in the generalized segment tree, in the order of an in-order traversal. You can also understand this as starting from only the root node $[1, n]$, and after reading each integer, splitting the node that currently contains this integer, eventually obtaining a generalized segment tree with $2n - 1$ nodes.

It is guaranteed that the given $n - 1$ integers form a permutation. It is not difficult to see that these pieces of information uniquely determine a generalized segment tree on $[1, n]$.

Output

Output a single integer representing the expected number modulo $p = 998244353$. That is, if the expected number is represented as an irreducible fraction $\frac{a}{b}$, you need to output an integer $c$ such that $c \times b \equiv a \pmod{p}$.

Examples

Input 1

3 1
1 2

Output 1

166374060

Note 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 tags is $1$. If the operation is $[1, 2]$, the number of tags is $2$. Thus the answer is $\frac{7}{6}$.

Input 2

5 4
2 1 3 4

Output 2

320443836

Input 3

See provided files.

Constraints

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