Given $n$ and $k$, let $p$ be a permutation of order $n$. You can partition $p$ into exactly $k$ non-empty contiguous segments (i.e., choose $k-1$ cut points $1 \le x_1 < x_2 < \cdots < x_{k-1} < n$ to form the segments $[1, x_1], (x_1, x_2], \dots, (x_{k-1}, n]$), and then sort the numbers within each segment in ascending order to obtain a new permutation $q$.

Define $f(p)$ as the lexicographically smallest permutation $q$ that can be obtained among all possible partition schemes.

Given a permutation $q$ of order $n$, find the number of permutations $p$ of order $n$ such that $f(p) = q$. Output the answer modulo $998244353$.

Input

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

The second line contains $n$ integers, representing the permutation $q$.

Output

Output a single integer representing the answer.

Examples

Input 1

2 1
1 2

Output 1

2

Input 2

3 3
3 1 2

Output 2

1

Input 3

6 3
1 2 3 6 5 4

Output 3

13

Constraints

For all data, $1 \le n \le 500, 1 \le k \le n$.

• Subtask 1 (10%): $n \le 6$.
• Subtask 2 (20%): $n \le 10$.
• Subtask 3 (30%): $q = (1, 2, \dots, n)$.
• Subtask 4 (40%): No special restrictions.