记录编号	39231	评测结果	AAAAAAAAAA
题目名称	奇怪的棋盘	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	1.081 s
提交时间	2012-07-07 17:33:27	内存使用	7.90 MiB

const maxn=501; yu=1000000007;
var
 height,h,w:array[0..maxn] of int64;
 tot,n,i,j,k:longint;
 a,c,ff,f:array[-1..maxn,-1..maxn] of int64;
 procedure build(l,r,level:longint);
 var i,j,min,v:longint;
 begin
  inc(tot);
  w[tot]:=r-l+1;
  h[tot]:=maxlongint;
  for i:=l to r do
   if height[i]<h[tot] then h[tot]:=height[i];
  min:=h[tot];
  h[tot]:=h[tot]-level+1;
  i:=l; v:=tot;
  repeat
   while (i<=r) and (height[i]<=min) do inc(i);
   j:=i;
   while (j<=r) and (height[j]>min) do inc(j);
   if i<=j-1 then
    begin
     inc(a[v,0]); a[v,a[v,0]]:=tot+1; build(i,j-1,min+1);
    end;
   i:=j;
  until i>r;
 end;
 function p(n,k:longint):int64;
 var i:longint; j:int64;
 begin
  j:=1;
  for i:=n-k+1 to n do j:=j*i mod yu;
  p:=j;
 end;
 procedure tree_dp(v:longint);
 var i,j,t:longint;
 begin
  if a[v,0]=0 then
   begin
    for i:=0 to k do
     if (w[v]>=i) and (h[v]>=i) then
      f[v,i]:=c[w[v],i]*p(h[v],i) mod yu;
    exit;
   end;
  for i:=1 to a[v,0] do
   tree_dp(a[v,i]);
  fillchar(ff,sizeof(ff),0);
  ff[0,0]:=1;
  for i:=1 to a[v,0] do
   for j:=0 to k do
    for t:=0 to j do
     ff[i,j]:=(ff[i-1,t]*f[a[v,i],j-t] mod yu+ff[i,j]) mod yu;
  for j:=0 to k do
   for i:=0 to j do
    if (w[v]-(j-i)>=i) and (h[v]>=i) then
     f[v,j]:=(c[w[v]-(j-i),i]*p(h[v],i) mod yu*
      ff[a[v,0],j-i] mod yu+f[v,j]) mod yu;
 end;
 procedure workc;
 var i,j:longint;
 begin
  c[0,0]:=1;
  for i:=1 to n do
   for j:=0 to i do
     c[i,j]:=(c[i-1,j-1]+c[i-1,j]) mod yu;
 end;
begin
 assign(input,'boarda.in'); reset(input);
 assign(output,'boarda.out'); rewrite(output);
 read(n,k);
 for i:=1 to n do read(height[i]);
 workc;
 build(1,n,1);
 tree_dp(1);
 writeln(f[1,k]);
 close(input); close(output);
end.