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. Each document has a serial number, and the pile was in order when her boss brought it in. Susan has been too lazy to put the documents that slid out of the pile back in place, so the order is no longer correct. Hearing that she has finished, the boss wants her to return the documents immediately in the document box he is sending her. The documents must go into the box in the order of their serial numbers.

The desk has room for exactly two more document piles, which Susan will use as temporary piles. She moves the documents in the current pile one by one, from the top, onto either of the two temporary piles. Making a pile too tall in haste would make it tumble, so each temporary pile can hold only a limited number of documents. After all documents are moved to the temporary piles and she receives the box, she moves the documents from the tops of the two piles, one by one, into the box. To put them into the box in order, each temporary pile must be in reverse order of serial numbers from top to bottom.

For example, suppose the pile has documents #1, #3, #4, #2, #6, and #5 from the top, and each temporary pile can hold at most 3 documents. Then she can form two temporary piles: one with #6, #4, and #3 from the top, and the other with #5, #2, and #1 (Figure E.1). Both piles are in reverse order. She then compares the serial numbers on top of the two piles and removes the document with the larger number (#6 in this case) first, putting it into the box. Repeating this puts all documents in the box in perfect order.

Figure E.1. Making two temporary piles

Susan wants to know whether the plan is feasible with the documents in the current pile and, if so, how many ways there are to stack them onto the two temporary piles. Write a program that computes this number for her. The answer is 0 if the plan is not feasible.

Each document in the pile can go to either temporary pile, so for n documents there are $2^n$ choice combinations in total. Some of them break the reverse order of a temporary pile, so they are not valid.

The example above corresponds to the first case of the sample input. In this case, the last two documents, #5 and #6, can swap their destinations. Exchanging the roles of the two temporary piles entirely is also allowed. Any other sequence of moves would make a pile taller than 3 or put a pile out of order, so the total number of ways in this example is $2 \times 2 = 4$.

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

n m
s1 . . . sn

Here, $n$ is the number of documents in the pile ($1 \le n \le 5000$), and $m$ is the number of documents that can be stacked in one temporary pile without risking a collapse ($n/2 \le m \le n$). Numbers $s_1$ through $s_n$ are the serial numbers of the documents in the pile, from top to bottom. It is guaranteed that every number from 1 through $n$ appears exactly once.

Output a single integer on one line: the number of ways to form two temporary piles that meet the objective. If the number of ways is at least $10^9 + 7$, output it modulo $10^9 + 7$. If no choice works, the number of ways is 0.