记录编号	39272	评测结果	AAAAAAAAAA
题目名称	奇怪的棋盘	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	1.644 s
提交时间	2012-07-08 14:43:19	内存使用	5.00 MiB

const
 inf=1000000007;
type
 stu=record 
  le,re,mid,land,lc,rc:longint;
 end;
var
 n,i,j,k,l,kk,tot:longint;
 h:array[1..502]of longint;
 f:array[0..1000,0..502]of int64;
 c:array[0..502,0..502]of longint;
 tree:array[1..1022]of stu;
 
 procedure make_tree(l,r,x,y:longint);
  var i,k:longint;mi:int64;
  begin
    //if r<l then exit;
   with tree[x] do 
	 begin 
      le:=l;re:=r;land:=y;
      if le=re then begin mid:=le;exit;end;
      mi:=maxlongint; 
      for i:=l to r do if h[i]<mi then 
		 begin mi:=h[i];k:=i;end;
	  mid:=k;
     end;   
	if l<=tree[x].mid-1 then 
	 begin inc(tot);tree[x].lc:=tot;make_tree(l,tree[x].mid-1,tot,mi);end;
	if tree[x].mid+1<=r then 
	 begin inc(tot);tree[x].rc:=tot;make_tree(tree[x].mid+1,r,tot,mi); end; 
  end;
 
 function dp(x,k:longint):int64;
  var i,hh,w,j:longint;
		 tt,tk:int64;
  begin
   if f[x,k]>-1 then exit(f[x,k]);
   //if k=0 then begin f[x,k]:=1;exit(1);end;  
   //if x=0 then begin f[x,k]:=0;exit(0);end;	   
   //if tree[x].le=0 then exit(0);
   if tree[x].le=tree[x].re then 
     begin 
       if (k>1) then f[x,k]:=0 else f[x,k]:=h[tree[x].le]-tree[x].land;
	   exit(f[x,k]);
	end;	   
   if tree[x].land=h[tree[x].mid] then 
	begin    
     f[x,k]:=0;
	 for i:=0 to k do 
		 begin 
	      tk:=dp(tree[x].lc,i);
	      if tk=0 then continue;
	      f[x,k]:=(f[x,k]+tk*dp(tree[x].rc,k-i) mod inf) mod inf;  
		 end; 
	 exit(f[x,k]);
	end;
	
   hh:=h[tree[x].mid]-tree[x].land;
   w:=tree[x].re-tree[x].le+1;
   if w<k then begin f[x,k]:=0;exit(0);end;
   f[x,k]:=0;
   for i:=0 to k do
    begin
      if i>hh then break;  
      tt:=c[w-k+i,i];   
	  for j:=hh downto hh-i+1 do tt:=(tt*j)mod inf;
	  for j:=0 to k-i do 	  
	   begin
	    tk:=dp(tree[x].lc,j);
	    if tk=0 then continue;
        f[x,k]:=(f[x,k]+((tt*tk)mod inf)*dp(tree[x].rc,k-i-j) mod inf)mod inf;
      end ;  
	end;  
	exit(f[x,k]); 
  end;	  
	  
begin
assign(input,'boarda.in');reset(input);
assign(output,'boarda.out');rewrite(output);	  
 readln(n,kk);
 for i:=1 to n do c[i,0]:=1;
 c[1,1]:=1;	c[0,0]:=1; 
 for i:=2 to n do 
  for j:=1 to i do c[i,j]:=(c[i-1,j-1]+c[i-1,j])mod inf;
	     
 for i:=1 to n do read(h[i]);
 tot:=1;
 make_tree(1,n,1,0);
 for i:=0 to tot do 
   for j:=1 to kk do f[i,j]:=-1;
 for i:=0 to tot do f[i,0]:=1;	  
 {for i:=1 to tot do 
	 begin
       writeln(tree[i].le,' ',tree[i].re,' ',tree[i].mid,' ',tree[i].land,' ',tree[i].lc,' ',tree[i].rc);
     end;
 writeln(dp(2,2)); halt;}
 writeln(dp(1,kk));
close(input);close(output); 
end.