从(1,1)到(n,m),每次向右或向下走一步,,不能经过(x,y),求走的方案数取模。 可以经过(x,y)则相当于m+n步里面选n步必须向下走,方案数为
再考虑其中经过(x,y)的方案数,也就是(1,1)到(x,y)的方案乘上(x,y)到(n,m)的方案,为
于是答案就是下式取模
m和n大到10的五次方,而组合数要用除法,所以要用费马小定理来求逆元。简单的说就是
而逆元用费马小定理和快速幂来算
最后减法取模记得要再加M再取一次模。
#include<bits/stdc++.h>
#define N 200005
#define M 1000000007
#define ll long long
using namespace std;
ll n,m,t,x,y,fac[N]= {1};
ll qpow(ll a,ll b)
{
ll ans=1;
ll k=a;
while(b)
{
if(b&1)ans=ans*k%M;
k=k*k%M;
b>>=1;
}
return ans;
}
ll C(ll n,ll m)
{
if(m>n)return 0;
return fac[n]*qpow(fac[m],M-2)%M*qpow(fac[n-m],M-2)%M;
}
int main()
{
for(int i=1; i<N; i++)fac[i]=fac[i-1]*i%M;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&x,&y);
printf("%lld\n",((C(n+m-2,n-1)-C(x+y-2,x-1)*C(n-x+m-y,n-x)%M+M)%M));
}
return 0;
}