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 3Sample Output 1
3Explanation
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 3Sample Output 2
17
Comments
nk orz
andrew q
shawn d
phoenix b
This comment is hidden due to too much negative feedback. Click here to view it.