Mountain, Valley And Repeat


Submit solution

Points: 17
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Given a permutation of the numbers \(1\) to \(N\), and a number \(K\), count number of subsequences of length \(K\) that are alternating.

A sequence \(x\) is a subsequence of a sequence \(y\) if \(x\) can be obtained from \(y\) by deletion of several (possibly, zero or all) elements. Two subsequences are different if the sequences of their indices are not the same.

An alternating sequence, \(S\), is one that follows the format \(S_1 > S_2 < S_3 > S_4 < S_5 \: ...\)

Formally, a sequence is called alternating if when \(i\) is odd \(S_i > S_{i+1}\) is satified and when \(i\) is even \(S_i < S_{i+1}\) is satified, for all \(1 \le i \lt \lvert S \rvert \).

Since the answer can be very large, output the answer modulo \(10^9+7\).

Constraints

\(2 \le N \le 10^5\)

\(2 \le K \le \min(N, 50)\)

\(1 \le P_i \le N\)

\(P_i \not = P_j \: (i \not = j)\)

Input Specification

The first line will contain two integers \(N\) and \(K\), the number of elements in the permutation and the required length of the subsequences, respectively.

The next line will contain \(N\) space-separated integers, \(P_i\), the elements of the permutation.

Output Specification

Output the number of subsequences that are of length \(K\) and are alternating modulo \(10^9+7\).

Sample Input 1

5 4
4 2 1 5 3

Sample Output 1

3

Explanation

There are only \(5\) subsequences of length \(4\)

\([4, 2, 1, 5], [4, 2, 5, 3], [4, 2, 1, 3], [2, 1, 5, 3], [4, 1, 5, 3]\)

Out of these only 3 are alternating: \([4, 2, 5, 3], [4, 1, 5, 3], [2, 1, 5, 3]\)

Sample Input 2

7 3
5 7 2 1 4 6 3

Sample Output 2

17

Comments


  • 4
    andrewq  commented on Oct. 22, 2022, 1:12 a.m.

    nk orz


    • 2
      shawnD  commented on Sept. 13, 2023, 10:42 p.m.

      andrew q


  • -14
    jjustinfang  commented on Oct. 20, 2022, 9:37 a.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.