28192번 - Record Parity 다국어

문제

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円$.

입력

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$.

출력

I'll let you guess this one.

제한

노트

In the second sample all of subsequences of length 3 have exactly 3 records, and none other subsequences have exactly 3 records, so the sum is equal to $(-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 of empty set is 0.