太神了，被数学题虐了
orz http://m.blog.csdn.net/blog/skywalkert/43970331
这道题关键是抓住m较小的特点，构造递推解决
1 const mo=1000000007; 2 3 var c:array[0..1010,0..1010] of longint; 4 f:array[0..1010] of int64; 5 i,j,n,m:longint; 6 t,ch:int64; 7 8 function quick(x:int64;y:longint):int64; 9 begin 10 quick:=1; 11 while y>0 do 12 begin 13 if y mod 2=1 then quick:=quick*x mod mo; 14 y:=y div 2; 15 x:=x*x mod mo; 16 end; 17 end; 18 19 begin 20 readln(n,m); 21 c[0,0]:=1; 22 for i:=1 to m do 23 begin 24 c[i,0]:=1; 25 for j:=1 to i do 26 c[i,j]:=(c[i-1,j]+c[i-1,j-1]) mod mo; 27 end; 28 if m=1 then 29 writeln(int64(n)*int64(n+1) div 2 mod mo) 30 else begin 31 ch:=quick(m-1,mo-2); 32 f[0]:=int64(m)*(quick(m,n)-1+mo) mod mo*ch mod mo; 33 for i:=1 to m do 34 begin 35 f[i]:=quick(n,i)*quick(m,n+1) mod mo; 36 for j:=0 to i-1 do 37 begin 38 t:=int64(c[i,j])*f[j] mod mo; 39 if (i-j) mod 2=1 then f[i]:=(f[i]-t+mo) mod mo 40 else f[i]:=(f[i]+t) mod mo; 41 end; 42 f[i]:=f[i]*ch mod mo 43 end; 44 writeln(f[m]); 45 end; 46 end.