문서 재정렬

수잔은 식탁을 편하게 배치하는 데는 능숙하지만 사무실 책상은 그렇지 않다.

수잔은 방금 문서 한 묶음의 서류 작업을 마쳤다. 문서들은 아직 책상 위에 쌓여 있다. 각 문서에는 일련번호가 있고, 상사가 가져왔을 때는 번호 순서대로 쌓여 있었다. 그런데 수잔이 게을러서 더미에서 빠져나온 문서를 제자리에 돌려놓지 않았고, 지금은 순서가 맞지 않는다. 수잔이 끝났다는 소식을 들은 상사는 문서를 곧바로 자신이 보내는 문서함에 넣어 돌려주기를 원한다. 문서는 당연히 일련번호 순서대로 문서함에 넣어야 한다.

책상에는 임시 더미를 두 개 더 만들 공간이 딱 맞게 있다. 수잔은 현재 더미의 문서를 위에서부터 하나씩 두 임시 더미 중 하나로 옮긴다. 서둘러 더미를 너무 높게 쌓으면 무너질 수 있으므로, 각 임시 더미에 올릴 수 있는 문서 수에는 제한이 있다. 모든 문서를 임시 더미로 옮기고 문서함을 받으면, 두 더미의 위쪽 문서부터 하나씩 꺼내 문서함에 넣는다. 문서함에 순서대로 넣으려면 각 임시 더미에서 위에서 아래로 갈수록 일련번호가 작아지는 역순으로 쌓여 있어야 한다.

예를 들어 더미의 위에서부터 문서 #1, #3, #4, #2, #6, #5가 있고 임시 더미에는 최대 3개까지만 올릴 수 있다고 하자. 그러면 위에서부터 #6, #4, #3으로 이루어진 더미 하나와 #5, #2, #1로 이루어진 더미 하나를 만들 수 있다(그림 E.1). 두 임시 더미 모두 역순이다. 이후 두 더미의 맨 위 문서 번호를 비교해서 큰 번호(이 경우 #6)를 가진 문서를 먼저 꺼내 문서함에 넣는다. 이를 반복하면 모든 문서가 문서함에 순서대로 들어간다.

그림 E.1. 두 임시 더미를 만드는 방법

수잔은 현재 더미의 문서로 이 계획을 실행할 수 있는지, 가능하다면 두 임시 더미에 문서를 쌓는 방법이 몇 가지인지 알고 싶어 한다. 이 수를 계산하는 프로그램을 작성해 수잔을 도와라. 계획이 실행 불가능하면 답은 0이다.

더미의 각 문서는 두 임시 더미 중 어느 쪽으로든 옮길 수 있으므로, 문서가 n개이면 선택 조합은 모두 $2^n$가지다. 그중 일부는 임시 더미의 역순을 깨뜨리므로 적절하지 않다.

위 예시는 입력 예제의 첫 번째 경우에 해당한다. 이 경우 마지막 두 문서인 #5와 #6은 행선지를 서로 바꿀 수 있다. 또 두 임시 더미의 역할을 통째로 맞바꿔도 된다. 다른 이동 순서는 더미 하나가 3개를 넘거나 순서가 어긋나므로, 이 예시에서 방법은 총 $2 \times 2 = 4$가지다.

입력은 다음 형식으로 주어지는 테스트 케이스 하나다.

n m
s1 . . . sn

여기서 $n$은 더미에 있는 문서 수($1 \le n \le 5000$)이고, $m$은 무너질 위험 없이 임시 더미 하나에 쌓을 수 있는 문서 수($n/2 \le m \le n$)다. $s_1$부터 $s_n$까지는 더미의 위에서 아래로 놓인 문서의 일련번호다. 1부터 $n$까지의 모든 수가 정확히 한 번씩 나타남이 보장된다.

두 임시 더미를 만드는 방법 중 조건을 만족하는 경우의 수를 정수 하나로 한 줄에 출력한다. 경우의 수가 $10^9 + 7$ 이상이면 $10^9 + 7$로 나눈 나머지를 출력한다. 어떤 선택으로도 계획이 성립하지 않으면 경우의 수는 0이다.