## Mountain, Valley And Repeat

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

nk orz

andrew q

shawn d

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