数学题，略蛋疼。可以证明最优的方案一定是先沿着较长边走，然后再走较短边。这样的话答案就是1+n+C1n+C2n+1+...+Cmn+m。然后由于答案是取模一个指数num，那么对于一个组合a/b，由费马小定理a/b mod num=a*b^(num-2) mod num。那么答案就可以用快速幂求得。这样时间复杂度就是mlogm，由于m是较短边，那么m<=1000000，而由于快速幂太慢，我开始T了好久，后来用位运算瞎搞搞A了。
program p3260; const num=1000000007; var n,m,k1,k2,tot:int64; i,j:longint; function quick(k1,k2:int64):int64; var k,i:int64; begin k:=k1; i:=1; while k2>0 do begin if k2 and 1>0 then i:=i*k mod num; k:=k*k mod num; k2:=k2 shr 1; end; exit(i); end; begin readln(n,m); if n<m then begin k1:=m; m:=n; n:=k1; end; n:=n mod num; tot:=n+1; k1:=1; k2:=1; for i:=1 to m do begin k1:=k1*i mod num; k2:=k2*(n+i) mod num; tot:=((tot+quick(k1,num-2)*k2) mod num); end; writeln(tot); end.
