## Mountain, Valley And Repeat

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

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

nk orz

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

andrew q

• commented on Sept. 26, 2023, 1:21 p.m.

shawn d

• commented on Nov. 14, 2023, 9:38 p.m.

phoenix b

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