太神了，被数学题虐了

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   begin10     quick:=1;11     while y>0 do12     begin13       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 begin20   readln(n,m);21   c[0,0]:=1;22   for i:=1 to m do23   begin24     c[i,0]:=1;25     for j:=1 to i do26       c[i,j]:=(c[i-1,j]+c[i-1,j-1]) mod mo;27   end;28   if m=1 then29     writeln(int64(n)*int64(n+1) div 2 mod mo)30   else begin31     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 do34     begin35       f[i]:=quick(n,i)*quick(m,n+1) mod mo;36       for j:=0 to i-1 do37       begin38         t:=int64(c[i,j])*f[j] mod mo;39         if (i-j)  mod 2=1 then f[i]:=(f[i]-t+mo) mod mo40         else f[i]:=(f[i]+t) mod mo;41       end;42       f[i]:=f[i]*ch mod mo43     end;44     writeln(f[m]);45   end;46 end.