Reordering the Documents

Susan is good at arranging her dining table for convenience, but not her office desk.

Susan has just finished the paperwork on a set of documents, which are still piled on her desk. They have serial numbers and were stacked in order when her boss brought them in. The ordering, however, is not perfect now, as she has been too lazy to put the documents slid out of the pile back to their proper positions. Hearing that she has finished, the boss wants her to return the documents immediately in the document box he is sending her. The documents should be stowed in the box, of course, in the order of their serial numbers.

The desk has room just enough for two more document piles where Susan plans to make two temporary piles. All the documents in the current pile are to be moved one by one from the top to either of the two temporary piles. As making these piles too tall in haste would make them tumble, not too many documents should be placed on them. After moving all the documents to the temporary piles and receiving the document box, documents in the two piles will be moved from their tops, one by one, into the box. Documents should be in reverse order of their serial numbers in the two piles to allow moving them to the box in order.

For example, assume that the pile has six documents #1, #3, #4, #2, #6, and #5, in this order from the top, and that the temporary piles can have no more than three documents. Then, she can form two temporary piles, one with documents #6, #4, and #3, from the top, and the other with #5, #2, and #1 (Figure E.1). Both of the temporary piles are reversely ordered. Then, comparing the serial numbers of documents on top of the two temporary piles, one with the larger number (#6, in this case) is to be removed and stowed into the document box first. Repeating this, all the documents will be perfectly ordered in the document box.

Figure E.1. Making two temporary piles

Susan is wondering whether the plan is actually feasible with the documents in the current pile and, if so, how many different ways of stacking them to two temporary piles would do. You are asked to help Susan by writing a program to compute the number of different ways, which should be zero if the plan is not feasible.

As each of the documents in the pile can be moved to either of the two temporary piles, for $n$ documents, there are $2^n$ different choice combinations in total, but some of them may disturb the reverse order of the temporary piles and are thus inappropriate.

The example described above corresponds to the first case of the sample input. In this case, the last two documents, #5 and #6, can be swapped their destinations. Also, exchanging the roles of two temporary piles totally will be OK. As any other move sequences would make one of the piles higher than three and/or make them out of order, the total number of different ways of stacking documents to temporary piles in this example is $2 \times 2 = 4$.

Input

The input consists of a single test case of the following format.

$n$ $m$
$s_1$ ...  $s_n$

Here, $n$ is the number of documents in the pile ($1 \leq n \leq 5000$), and $m$ is the number of documents that can be stacked in one temporary pile without committing risks of making it tumble down ($n/2 \leq m \leq n$). Numbers $s_1$ through $s_n$ are the serial numbers of the documents in the document pile, from its top to its bottom. It is guaranteed that all the numbers $1$ through $n$ appear exactly once.

Output

Output a single integer in a line which is the number of ways to form two temporary piles suited for the objective. When no choice will do, the number of ways is $0$, of course.

If the number of possible ways is greater than or equal to $10^9 + 7$, output the number of ways modulo $10^9 + 7$.

Sample Input 1

6 3
1 3 4 2 6 5

Sample Output 1

4

Sample Input 2

6 6
1 3 4 2 6 5

Sample Output 2

8

Sample Input 3

4 4
4 3 1 2

Sample Output 3

0

---