Susan は食卓を使いやすく整えるのが得意ですが、職場の机を整えるのは得意ではありません。

Susan は一組の書類の事務処理を終えたばかりで、書類はまだ机の上に積まれています。書類には通し番号があり、上司が持ってきたときは順番に積まれていました。しかし、Susan が山から抜き出した書類を元の位置に戻すのを面倒がったため、今は完全な順番ではありません。処理が終わったと聞いた上司は、これから送る書類箱に入れて直ちに返すよう求めています。もちろん、箱の中には通し番号の順に書類を収めなければなりません。

机には書類の山をあと $2$ つ置くのにちょうど足りる空間があり、Susan はそこに一時的な山を $2$ つ作るつもりです。現在の山のすべての書類を上から $1$ 枚ずつ取り、どちらかの一時的な山へ移します。急いで高く積みすぎると崩れるため、あまり多くの書類を積んではいけません。すべてを一時的な山に移して書類箱を受け取った後、両方の山の上から $1$ 枚ずつ箱へ移します。順番に箱へ移せるよう、両方の山の書類は通し番号の逆順でなければなりません。

例えば、現在の山に上から $1,3,4,2,6,5$ の順で $6$ 枚の書類があり、一時的な山には高々 $3$ 枚しか積めないとします。上から $6,4,3$ の山と $5,2,1$ の山を作れます（図参照）。どちらも逆順です。両方の山の一番上の書類の番号を比べ、大きい方（この場合は $6$）を先に取り出して箱へ入れます。これを繰り返すと、すべての書類が箱の中で完全に整列します。

Susan は現在の山の書類でこの計画が実行可能か、可能ならば一時的な $2$ つの山への積み方が何通りあるかを考えています。その通り数を計算するプログラムを書いて Susan を助けてください。実行不可能ならば通り数は $0$ とします。

各書類はどちらの一時的な山へも移せるため、$n$ 枚の書類について選択の組合せは全部で $2^n$ 通りあります。ただし、一部の組合せは一時的な山の逆順を崩すため不適切です。

上の例は入力例の最初のケースに対応します。この場合、最後の $2$ 枚の書類 $5$ と $6$ の移動先を交換できます。また、$2$ つの一時的な山の役割を完全に交換しても構いません。他の移動順序では一方の山が $3$ 枚より高くなるか、順番が崩れるか、あるいはその両方になるため、この例で一時的な山に書類を積む方法の総数は $2\times2=4$ です。

入力

入力の最初の行には $2$ つの整数 $n,m$ が含まれます。$n$ は山にある書類の枚数（$1\le n\le5000$）、$m$ は崩れる危険を冒さず一時的な山に積める枚数（$n/2\le m\le n$）です。次の行には $s_1$ から $s_n$ までの数が含まれ、山の上から下の順に書類の通し番号を表します。$1$ から $n$ までのすべての数がちょうど $1$ 回ずつ現れることが保証されます。

出力

目的に適した $2$ つの一時的な山を作る方法の数を表す整数を $1$ 行に出力してください。

どの選択でも不可能ならば、当然通り数は $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