rt，不过不是luogu上，学校OJ限时只有1s，而且数据也要强一点，被卡哩。

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
#define LL long long

const int N = 510, M = 1e6 + 10, mod = 1e9 + 7;
int n, k, h[N];
int f[N][N];
int tot;

inline int mo(int x)
{
	return x < mod ? x : x - mod;
}

inline LL ksm(LL x, LL y)
{
	LL res = 1;
	x %= mod;
	while(y)
	{
		if(y & 1) res = res * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return res;
}

int fac[M], inv[M];
inline void init(int n)
{
	fac[0] = 1;
	for(register int i = 1; i <= n; i = -~i)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = ksm(fac[n], mod - 2);
	for(register int i = n - 1; i >= 0; i = ~-i)
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

inline int C(int n, int m)
{
	if(n < m) return 0;
	return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}

inline int dp(int l, int r, int d)
{
	if(l > r) return 0;
	
	int minn = 0;
	for(register int i = l; i <= r; i = -~i)
		if(h[i] < h[minn]) minn = i;
	
	int x = dp(l, ~-minn, h[minn]), y = dp(-~minn, r, h[minn]);
	tot = -~tot;
	for(register int i = 0; i <= k; i = -~i)
		for(register int j = 0; j <= i; j = -~j)
			f[tot][i] = mo(f[tot][i] + 1ll * f[x][j] * f[y][i - j] % mod);
	int len = r - l + 1;
	for(register int i = k; i >= 0; i = ~-i)
		for(register int j = 1; j <= i; j = -~j)
			f[tot][i] = mo(f[tot][i] + 1ll * f[tot][i - j] * C(h[minn] - d, j) % mod * C(len - i + j, j) % mod * fac[j] % mod);
	
	return tot;
}

int main()
{
	init(1e6);
	
	scanf("%d%d", &n, &k);
	for(register int i = 1; i <= n; i = -~i)
		scanf("%d", &h[i]);
	h[0] = 1e9;
	
	f[0][0] = 1;
	printf("%d\n", f[dp(1, n, 0)][k]);
	return 0;
}