按列高建立笛卡尔树，转成树上问题......
笛卡尔树是什么？
它一般是针对序列建立的，是下标的BST和权值的堆(即中序遍历是原序列连续区间，节点权值满足堆性质)，这里不讲具体怎么建树(放在知识总结里了)。我们想一想对于一个序列建出来的树长啥样(灵魂画师上线辣)
也就是说树上一个节点对应原图上一个矩形区域，这样我们就把原序列转成了一个组合问题。设$dp[i][j]$表示以$i$为根的子树的区域里放了$j$个车的方案数，那么先是子树里的放法。呃，这不就是树形背包吗。。。转移不写了
然后考虑在自己的矩形里的放法，我们枚举放了$k$个车，那么$dp[i][j]$可以从$dp[i][j-k]$转移过来，过程是这$k$个车排列($k!$)+行上组合($h[i]-h[fa[i]]$里选$k$个)+列上组合($siz[i]-j+k$)
注意：上下两个转移都不要啥也不放就转移，这时候显然是假的=。=
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=1e6+,mod=1e9+;
int fac[M],inv[M],fth[N],son[N][];
int a[N],stk[N],siz[N],dp[N][N];
int n,k,top,root;
void Add(int &x,int y)
{
x+=y;
if(x>=mod) x-=mod;
}
int Qpow(int x,int k)
{
if(k==) return x;
int tmp=Qpow(x,k/);
return k%?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
int C(int a,int b)
{
return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void Pre()
{
fac[]=inv[]=;
for(int i=;i<=;i++) fac[i]=1ll*fac[i-]*i%mod;
inv[]=Qpow(fac[],mod-);
for(int i=;i;i--) inv[i]=1ll*inv[i+]*(i+)%mod;
}
void DFS(int nde)
{
siz[nde]=dp[nde][]=;
for(int i=,g;i<=;i++)
if(g=son[nde][i])
{
DFS(g);
for(int j=min(siz[nde],k);~j;j--)
for(int h=min(siz[g],k-j);h;h--)
Add(dp[nde][j+h],1ll*dp[nde][j]*dp[g][h]%mod);
siz[nde]+=siz[g];
}
int col=a[nde]-a[fth[nde]];
for(int i=min(siz[nde],k);~i;i--)
{
int tmp=;
for(int j=min(i,col);j;j--)
Add(tmp,1ll*dp[nde][i-j]*fac[j]%mod*C(col,j)%mod*C(siz[nde]-i+j,j)%mod);
Add(dp[nde][i],tmp);
}
}
int main()
{
scanf("%d%d",&n,&k),Pre();
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
while(top&&a[stk[top]]>a[i])
{
int nde=stk[top]; top--;
if(top&&a[stk[top]]>a[i])
son[stk[top]][]=nde,fth[nde]=stk[top];
else
son[i][]=nde,fth[nde]=i;
}
stk[++top]=i;
}
while(top>)
{
son[stk[top-]][]=stk[top];
fth[stk[top]]=stk[top-],top--;
}
// for(int i=1;i<=n;i++) printf("%d %d\n",son[i][0],son[i][1]);
root=stk[],DFS(root);
printf("%d",dp[root][k]);
return ;
}