这题刚看完，想了想，没思路，就题解了 = =
但不得不说，找到这个题解真的很强大，链接：http://blog.csdn.net/qwb492859377/article/details/51478117
这个我只是看了他的思路，之后代码就自己写，之后交上去就是1A，我感觉好的题解就应该是这样的，Orz
要先看下他的思路，现在我在补充些我的理解： 首先，你要把行，列分开看，先说行，从1到n，1和n都不能走，因为1是开始，n是确定的，所以你有n-2种选择，你可以枚举x从1到n-2，就相当于高中学的，在n-2个箱子中放x个相同小球，有几种情况？ 同理，列也是，但注意在同一个x时他们还要相乘，这很明显，因为不可能相加。
最后ans还要加1，因为从1,1直接到n,m的这种情况还没算。还有就是算C（n，k）了，这就是套模板了，没什么说的。
#include <bits/stdc++.h>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long ll;
#define PI(A) printf("%d\n",A)
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++)
#define reRep(i,a,b) for(int i=(a);i>=(b);i--)
const double EPS= 1e- ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ const int MAXN= + ;
const int MOD=1e9+ ;
ll jiech[MAXN];//求阶乘取完模的数组 int N,M; //快速幂模板
ll mod_pow(ll x,ll n,ll mod)
{
ll res=;
while(n>){
if (n&) res=res*x%mod;
x=x*x%mod;
n>>=;
}
return res;
} //求C(n,k)的函数 （n在C下面，k在C上面）
//限制：MOD必须是质数，因为是用费马小定理求的
ll C(int n,int k)
{
ll d=(jiech[k]*jiech[n-k])%MOD;
return (jiech[n]*mod_pow(d,MOD-,MOD))%MOD;
} int main()
{
//先打表阶乘取模数组
jiech[]=jiech[]=;
for (int i=;i<MAXN;i++)
{
jiech[i]=(jiech[i-]*i)%MOD;
} while(~SII(N,M))
{ int k=min(N,M);
int k2=max(N,M);
ll ans=;
//要根据小的那个循环
for (int i=;i<=k-;i++)
{
ans+=C(k-,i)*C(k2-,i);
ans%=MOD;
}
printf("%lld\n",ans+);
} return ;
}