//nCr and [houjyo-genri] //yukicoder No.802 #include #define mod 1000000007 long long power(long long a,long long b){ long long x=1,y=a; while(b>0){ if(b&1ll){ x=(x*y)%mod; } y=(y*y)%mod; b>>=1; } return x%mod; } long long modular_inverse(long long n){ return power(n,mod-2); } long long factorial[4194304]; long long invfact[4194304]; void cfact(){ long long i; factorial[0]=1; factorial[1]=1; for(i=2;i<4194304;i++){ factorial[i]=factorial[i-1]*i; factorial[i]%=mod; } invfact[4194303]=modular_inverse(factorial[4194303]); for(i=4194302;i>=0;i--){ invfact[i]=invfact[i+1]*(i+1); invfact[i]%=mod; } } long long calcnCr(long long n,long long k){ if(k<0 || n-k<0){return 0;} return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod; } int main(void){ cfact(); long long i,j,n,m,k,a,b,c,h,w,r=0,l,t,d1,d; scanf("%lld%lld",&n,&m); scanf("%lld%lld",&d1,&d); m-=(d1*(n-1)); d-=d1; //手を付けやすいように、A_iからd1*(i-1)を引いて条件を以下のように変換する。 //1 <= A_1 <= A_2 <= ... <= A_n <= m //0 <= A_{i+1} - A_i <= d //条件(数え上げるべきものはこれら全てに違反するもので必要十分) //条件i : d < A_{i+1} - A_i //包除原理でこれら全てに違反するものを数え上げれば、それが解 k=1; r=0; for(i=0;i<=n-1;i++){ //i個の条件に違反する(「「それ以外はどちらでもよい」」) //まず、違反する条件をi個選ぶ。 c=calcnCr(n-1,i); //このとき、ある条件iに違反するなら、A_{i+1}以降をすべて-(d+1)すればよい。 //これで条件iには確実に違反できる。 //繰り返しになるが、他の条件は「「満たしても満たさなくてもどちらでもよい」」 //この条件たちを変換すると結局 //0 <= B_1 <= B_2 <= ... <= B_n <= m-(d+1)*i-1 //を満たす数列Bをすべて数え上げることになる。 //これは // o が m-(d+1)*i-1 個、 | がn個の数え上げである。 c*=calcnCr((m-(d+1)*i-1)+n,n); c%=mod; //あとは(-1)^nを掛けるあれ。 r+=mod; r+=(c*k); r%=mod; k*=-1; } printf("%lld\n",r); return 0; }