Record Parity

Time limit1sMemory limit1024 MB

Summary

Given a permutation, find the sum of (-1)^len over all subsequences with exactly k records (left-to-right maxima), modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

You are given a permutation of length $n$ and an integer $k$ .

An element is called a record if it is strictly greater than all the elements before it.

Calculate the sum of $(-1)^{\mathit{len}}$ over all subsequences that have exactly $k$ records. Here $\mathit{len}$ is the number of elements in the subsequence. Since the answer can be large, calculate it modulo $998\,244\,353$ .

Input

The first line contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^6$ ).

The second line contains the permutation $p_1, p_2, \ldots, p_n$ .

Output

I'll let you guess this one.

Hint

In the second sample, all subsequences of length 3 have exactly 3 records, and no other subsequence has exactly 3 records. The sum is therefore $(-1)^3 \binom{7}{3} = -35$ , which is $998\,244\,318$ modulo $998\,244\,353$ .

In the third sample, none of the subsequences have exactly 5 records, and the sum over the empty set is 0.

Examples3

Example 1
Input
```
5 2
4 1 2 5 3
```
Expected output
```
3
```
Example 2
Input
```
7 3
1 2 3 4 5 6 7
```
Expected output
```
998244318
```
Example 3
Input
```
5 5
2 5 4 1 3
```
Expected output
```
0
```