Problem: 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.

<image>
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






Example

Input

6 3
1 3 4 2 6 5


Output

4

Solution (in CPP):

Solution:
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void ckmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void ckmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()
using VI=vector<int>;

template<typename base_type, base_type _MOD>
class IntMod
{
public:
	static const int INVERSE_CACHE_SIZE = (1 << 20);
	static base_type MOD;
	static void set_mod(base_type new_mod) { MOD = new_mod; }

	base_type n;

	IntMod(long long d = 0) { n = (d >= 0 ? d % MOD : (d % MOD + MOD) % MOD); }
	virtual ~IntMod() = default;

	IntMod operator-() const { return build(n == 0 ? 0 : MOD - n); }
	IntMod& operator+=(IntMod a) { n = (n >= MOD - a.n ? n - MOD + a.n : n + a.n); return *this; }
	IntMod& operator-=(IntMod a) { n = (n >= a.n) ? n - a.n : n - a.n + MOD; return *this; }
	IntMod& operator*=(IntMod a) { *this = *this * a; return *this; }
	IntMod& operator/=(IntMod a) { *this = *this / a; return *this; }

	static IntMod build(base_type n) { IntMod r; r.n = n; return r; }

	static base_type inverse_cache[INVERSE_CACHE_SIZE];
	static bool inverse_cache_ready;
	friend IntMod inverse(IntMod n) { return build(inverse_internal(n.n)); }
	static base_type inverse_internal(base_type n)
	{
		if (!inverse_cache_ready) 
		{
			inverse_cache_ready=true;
			inverse_cache[0] = 0;
			inverse_cache[1] = 1;
			for (int n = 2; n < INVERSE_CACHE_SIZE; ++n) inverse_cache[n] = (MOD - (base_type)((long long)inverse_cache[MOD % n] * (MOD / n) % MOD));
		}
		return n < INVERSE_CACHE_SIZE ? inverse_cache[n] : MOD - (base_type)((long long)inverse_internal(MOD % n) * (MOD / n) % MOD);
	}

	friend bool operator==(IntMod a, IntMod b) { return a.n == b.n; }
	friend bool operator!=(IntMod a, IntMod b) { return a.n != b.n; }
	friend IntMod operator+(IntMod a, IntMod b) { return build(a.n >= MOD - b.n ? a.n - MOD + b.n : a.n + b.n); }
	friend IntMod operator-(IntMod a, IntMod b) { return build(a.n >= b.n ? a.n - b.n : a.n - b.n + MOD); }
	friend IntMod operator*(IntMod a, IntMod b) { return build(static_cast<base_type>(static_cast<long long>(a.n) * b.n % MOD)); }
	friend IntMod operator/(IntMod a, IntMod b) { return a * inverse(b); }
	friend IntMod pow(IntMod p, long long e)
	{
		if (e <= 0) return IntMod(1);
		IntMod r = IntMod(1);
		while (1) { if (e & 1) r *= p; e /= 2; if (e) p = p * p; else break; }
		return r;
	}

	friend istream& operator>>(istream &stream, IntMod &a) { stream >> a.n; return stream; }
	friend ostream& operator<<(ostream &stream, const IntMod &a) { stream << a.n; return stream; }
};
template<typename base_type, base_type _MOD> base_type IntMod<base_type, _MOD>::inverse_cache[INVERSE_CACHE_SIZE];
template<typename base_type, base_type _MOD> bool IntMod<base_type, _MOD>::inverse_cache_ready;
template<typename base_type, base_type _MOD> base_type IntMod<base_type, _MOD>::MOD = _MOD;

#define MOD (1000000007)
using Int = IntMod<int, MOD>;

const int maxsize=200000;

Int permutation[maxsize];
Int permutation_inv[maxsize];

Int choose(int n,int m)
{
	return (m<0 || m>n?0:permutation[n]*permutation_inv[m]*permutation_inv[n-m]);
}
void prepare()
{
	permutation[0]=permutation_inv[0]=1;
	FOR(i,1,maxsize)
	{
		permutation[i]=permutation[i-1]*i;
		permutation_inv[i]=permutation_inv[i-1]/i;
	}
}

void expand(vector<Int>& f,int cnt)
{
	int n=SIZE(f)-1;
	for (;cnt>0;--cnt)
		for (int i=n;i>0;i--)
			f[i]+=f[i-1];
}

int solve(VI a,int m)
{
	int n=SIZE(a);
	if (n==1) return 2;
	vector<Int> f(n+1);
	f[0]=1;
	int c1=0,c2=0;
	for (int k=0;k<n;)
	{
		if (c1>a[k]) return 0;
		int p=k;
		for (;p+1<n && a[p]<a[p+1];++p);
		if (p>=n-1)
		{
			for (;k<n && a[k]<c2;k++);
			expand(f,n-k);
			Int ret=0;
			for (int c1=0;c1<=m;c1++) if (n-c1<=m) ret+=f[c1];
			return ret.n;
		}
		if (c2>a[p]) return 0;
		for (;a[k]<c2;k++) c1=a[k];
		if (c1>a[p+1]) return 0;
		int key=a[p+1];
		int cnt=0;
		for (;a[k]<key;k++) cnt++;
		expand(f,cnt);
		vector<Int> g(n+1);
		int cnt2=p-k+1;
		int ep=(c2<a[p+1]);
		REP(c1,SIZE(f)) if (f[c1].n)
		{
			if (c1+cnt2<=n) g[c1+cnt2]+=f[c1];
			if (ep)
			{
				int c2=k-c1;
				if (c2+cnt2<=n) g[c2+cnt2]+=f[c1];
			}
		}
		f.swap(g);
		c2=a[p];
		c1=a[p+1];
		k=p+2;
	}
	Int ret=0;
	for (int c1=0;c1<=m;c1++) if (n-c1<=m) ret+=f[c1];
	return ret.n;
}
int main()
{
#ifdef _MSC_VER
	freopen("input.txt","r",stdin);
#endif
	std::ios::sync_with_stdio(false);
	prepare();
	/*
	int ee=solve(VI{3,1,4,2},2);
	printf("ee = %d\n",ee);
	for (int n=1;n<=8;n++)
	{
		printf("n = %d\n",n);
		VI p(n);
		REP(i,n) p[i]=i+1;
		do{
			for (int m=(n+1)/2;m<=n;m++)
			{
				int r1=solve(p,m);
				int r2=0;
				REP(set,two(n))
				{
					int p1=0,p2=0,c1=0,c2=0;
					int ok=1;
					REP(i,n)
						if (contain(set,i))
						{
							if (p[i]<p1) ok=0;
							p1=p[i];
							++c1;
						}
						else
						{
							if (p[i]<p2) ok=0;
							p2=p[i];
							++c2;
						}
					if (ok && c1<=m && c2<=m) ++r2;
				}
				if (r1!=r2)
				{
					printf("ERROR\n");
				}
			}
		} while (next_permutation(ALL(p))!=0);
	}
	*/
	int n,m;
	while (cin>>n>>m && n!=0)
	{
		VI a(n);
		REP(i,n) cin>>a[i];
		int ret=solve(a,m);
		printf("%d\n",ret);
#ifndef _MSC_VER
		break;
#endif
	}
	return 0;
}