Susan은 식탁을 편리하게 정리하는 데는 능숙하지만, 사무실 책상은 그렇지 않다.

Susan은 방금 여러 문서의 서류 작업을 마쳤고, 문서들은 아직 책상에 쌓여 있다. 문서에는 일련번호가 있고, 상사가 가져왔을 때는 순서대로 쌓여 있었다. 하지만 Susan이 더미에서 꺼낸 문서들을 제자리에 넣기 귀찮아했기 때문에 지금은 순서가 완벽하지 않다. 작업이 끝났다는 말을 들은 상사는 보내고 있는 문서 상자에 문서들을 담아 즉시 돌려주기를 원한다. 물론 문서들은 상자 안에 일련번호 순서대로 들어 있어야 한다.

책상에는 문서 더미 두 개를 더 놓을 공간만 있으며, Susan은 그곳에 임시 더미 두 개를 만들려고 한다. 현재 더미의 모든 문서를 맨 위에서 하나씩 꺼내 두 임시 더미 중 하나로 옮겨야 한다. 급히 너무 높게 쌓으면 더미가 무너질 수 있으므로 너무 많은 문서를 올려서는 안 된다. 모든 문서를 임시 더미로 옮기고 문서 상자를 받으면, 두 더미의 맨 위에서 문서를 하나씩 꺼내 상자에 넣는다. 상자에 순서대로 옮길 수 있도록 두 더미의 문서는 일련번호의 역순이어야 한다.

예를 들어 현재 더미에 위에서부터 $1,3,4,2,6,5$ 순서로 여섯 문서가 있고, 임시 더미에는 문서를 최대 세 개까지만 놓을 수 있다고 하자. 위에서부터 $6,4,3$인 더미와 $5,2,1$인 더미를 만들 수 있다(그림 참고). 두 임시 더미 모두 역순으로 정렬되어 있다. 두 임시 더미의 맨 위 문서의 일련번호를 비교하여 더 큰 번호의 문서(이 경우 $6$)를 먼저 꺼내 상자에 넣는다. 이를 반복하면 상자 안의 모든 문서가 완벽하게 정렬된다.

Susan은 현재 더미의 문서들로 이 계획을 실행할 수 있는지, 가능하다면 임시 더미 두 개에 문서를 쌓는 서로 다른 방법이 몇 가지인지 궁금하다. 이를 구하는 프로그램을 작성하여 Susan을 도와야 한다. 계획이 불가능하다면 방법의 수는 $0$이어야 한다.

더미의 각 문서는 두 임시 더미 중 어느 쪽으로든 옮길 수 있으므로 문서 $n$개에 대한 선택 조합은 총 $2^n$개이다. 하지만 일부 조합은 임시 더미의 역순을 깨뜨려 부적절하다.

위 예는 예제 입력의 첫 번째 경우에 해당한다. 이 경우 마지막 두 문서 $5$와 $6$의 목적지를 서로 바꿀 수 있다. 두 임시 더미의 역할을 완전히 바꾸어도 된다. 다른 이동 순서는 더미 중 하나에 문서가 세 개보다 많이 쌓이게 하거나 순서를 어긋나게 하므로, 이 예에서 임시 더미로 문서를 옮기는 서로 다른 방법의 총수는 $2\times2=4$이다.

입력

입력의 첫 줄에는 두 정수 $n,m$이 주어진다. $n$은 현재 더미의 문서 수 ($1\le n\le5000$)이고, $m$은 무너질 위험 없이 임시 더미 하나에 쌓을 수 있는 문서 수 ($n/2\le m\le n$)이다. 다음 줄에는 $s_1$부터 $s_n$까지의 수가 주어지며, 현재 문서 더미의 위에서 아래 순서로 문서의 일련번호를 나타낸다. $1$부터 $n$까지의 모든 수가 정확히 한 번씩 나타남이 보장된다.

출력

목적에 맞는 임시 더미 두 개를 만드는 방법의 수를 나타내는 정수 하나를 한 줄에 출력한다.

어떤 선택도 가능하지 않다면 당연히 방법의 수는 $0$이다. 가능한 방법의 수가 $10^9+7$ 이상이면 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.

예제

입력 1

6 3
1 3 4 2 6 5

출력 1

4

입력 2

6 6
1 3 4 2 6 5

출력 2

8

입력 3

4 4
4 3 1 2

출력 3

0