레코드 패리티

길이가 $n$인 순열 $p$와 정수 $k$가 주어진다.

어떤 원소가 자기 앞의 모든 원소보다 엄격하게 크면 그 원소를 레코드라고 한다.

정확히 $k$개의 레코드를 갖는 모든 부분수열에 대해 $(-1)^{\mathit{len}}$의 합을 구하라. 여기서 $\mathit{len}$은 부분수열의 원소 개수이다. 답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다.

첫 번째 줄에 정수 $n$과 $k$가 주어진다 ($1 \le k \le n \le 10^6$).

두 번째 줄에 순열 $p_1, p_2, \ldots, p_n$이 주어진다.

직접 맞춰 보세요.

두 번째 예제에서는 길이가 3인 부분수열이 모두 레코드를 정확히 3개씩 가지고, 다른 부분수열은 레코드가 정확히 3개인 경우가 없다. 따라서 합은 $(-1)^3 \binom{7}{3} = -35$이고, 이를 $998\,244\,353$으로 나눈 나머지는 $998\,244\,318$이다.

세 번째 예제에서는 레코드가 정확히 5개인 부분수열이 하나도 없으므로, 공집합의 합인 0이 답이다.