题解：
第一道笛卡尔树dp
会发现以一个点为分界 如果左边大于它右边大于它 那么大于的那部分是相互不影响的
于是我们对序列建立笛卡尔树
满足父亲节点的v<儿子节点的v 然后这棵树的中序遍历为原序列
这样子我们就可以dp了
考虑一个矩形的方案数
$C(n,i)*C(m,i)*i!$ 其中$i!$表示行列*匹配
然后现在的话我们只需要统计当前点包含的行数-用掉的 以及 列
另外处理逆元前缀积有一个比正着递推常数小的方法。。（少了取模和除法运算）
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for(int i=h;i<=t;i++)
#define dep(i,t,h) for(int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
namespace IO{
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T> void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
char sr[<<],z[]; int Z,C1=-;
template<class T>void wer(T x)
{
if (x<) sr[++C1]='-',x=-x;
while (z[++Z]=x%+,x/=);
while (sr[++C1]=z[Z],--Z);
}
IL void wer1()
{
sr[++C1]=' ';
}
IL void wer2()
{
sr[++C1]='\n';
}
template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}
template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}
template<class T>IL T MAX(T x,T y){return x>y?x:y;}
template<class T>IL T MIN(T x,T y){return x<y?x:y;}
};
using namespace IO;
const int N=;
const int N1=1e6+;
const int N2=1e6;
const int mo=1e9+;
int n,k,v[N],s[N],t,ls[N],rs[N];
int jc[N1],jc2[N1];
int dp[N][N],w[N];
ll tmp[N];
int ksm(int x,int y)
{
if (y==) return();
if (y==) return(x);
int k=ksm(x,y/);
k=1ll*k*k%mo;
if (y%==) k=1ll*k*x%mo;
return k;
}
int C(int x,int y)
{
if (x<y) return();
return 1ll*jc[x]*jc2[y]%mo*jc2[x-y]%mo;
}
void dfs(int x,int y)
{
w[x]=;
if (ls[x])
{
dfs(ls[x],v[x]); w[x]+=w[ls[x]];
}
if (rs[x])
{
dfs(rs[x],v[x]); w[x]+=w[rs[x]];
}
me(tmp);
rep(i,,w[x])
{
ll y=;
rep(j,,i)
y+=1ll*dp[ls[x]][j]*dp[rs[x]][i-j]%mo;
tmp[i]=y%mo;
}
rep(i,,w[x])
rep(j,,i)
(dp[x][i]+=1ll*tmp[j]*C(v[x]-y,i-j)%mo
*C(w[x]-j,i-j)%mo*jc[i-j]%mo)%=mo;
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(k);
int rt;
rep(i,,n)
{
read(v[i]);
bool tt=;
while (v[i]<v[s[t]]) t--,tt=;
rs[s[t]]=i;
if (tt) ls[i]=s[t+];
s[++t]=i;
}
rt=rs[];
jc[]=; jc2[]=;
rep(i,,N2) jc[i]=1ll*jc[i-]*i%mo;
jc2[N2]=ksm(jc[N2],mo-);
dep(i,N2-,) jc2[i]=1ll*jc2[i+]*(i+)%mo;
dp[][]=;
dfs(rt,);
cout<<dp[rt][k]<<endl;
return ;
}