fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int mod=1e9+7;
  5. ll exponentiation(ll base,ll power)
  6. {
  7. ll ans=1;
  8. while(power>0)
  9. {
  10. if(power%2==1)
  11. ans=(ans*base)%mod;
  12. base=(base*base)%mod;
  13. power/=2;
  14. }
  15. return ans%mod;
  16. }
  17.  
  18. ll inverse_mod(ll exp,ll base){ return (exp%mod*(exponentiation(base,mod-2))%mod)%mod; }
  19. ll factorial[1000100];
  20. ll binomial(ll a,ll b)
  21. {
  22. ll top=factorial[a];
  23. ll below=factorial[b];
  24. below=(below*factorial[a-b])%mod;
  25. ll ans=inverse_mod(top,below);
  26. return ans;
  27. }
  28.  
  29. int main()
  30. {
  31. factorial[0]=factorial[1]=1;
  32. for(ll i=2;i<1000100;i++)
  33. factorial[i]=(i*factorial[i-1])%mod;
  34. long long int ans=0,t,x1,x2,y1,y2;
  35. cin>>t;
  36. for(int j=1;j<=t;j++)
  37. {
  38. ans=0;
  39. cin>>x1>>y1>>x2>>y2;
  40. for(int i=0;i<=min(x2-x1,y2-y1);i++)
  41. {
  42. ll firstpart=(binomial(x2-x1+y2-y1-2*i,y2-y1-i));
  43. ll secondpart=binomial(x2-x1+y2-y1-i,i);
  44. ll temp=(firstpart*secondpart*1LL)%mod;
  45. ans=(ans+temp)%mod;
  46. }
  47. cout<<"Case "<<j<<": "<<ans<<endl;
  48. }
  49. return 0;
  50. }
  51.  
Success #stdin #stdout 0s 23056KB
stdin
3

1 2 2 3

2 2 3 3

3 4 3 5
stdout
Case 1: 3
Case 2: 3
Case 3: 1