fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mod 1000003
  3. using namespace std;
  4. typedef long int ll;
  5. vector < ll >factoz(mod,1);
  6.  
  7. ll POW(ll a,ll b){
  8. ll x=1,y=a;
  9. while(b>0){
  10. 	if(b%2==1){
  11. 		x=(x*y);
  12. 		if(x>mod)x%=mod;
  13. 		}
  14. 		y=(y*y);
  15. 		if(y>mod)y%=mod;
  16. 		b/=2;
  17. 	}
  18. 	return x;
  19. }
  20.  
  21. ll invE(ll n){
  22. return POW(n,mod-2);	
  23. }
  24.  
  25. ll smallcombinatorial(ll n,ll r){
  26. return (factoz[n]*((invE(factoz[r]))*(invE(factoz[n-r]))%mod))%mod;
  27. }
  28.  
  29. ll combinatorial(ll n,ll r){
  30. if(n==0&&r==0)return 1;
  31. ll ni,ri;
  32. ni=n%mod;
  33. ri=r%mod;
  34. if(ri>ni)return 0;
  35. return combinatorial(n/mod,r/mod)*smallcombinatorial(ni,ri);
  36. }
  37.  
  38. int main(){
  39. for(ll i=2;i<mod;i++)
  40. factoz[i] = (factoz[i-1]*i)%mod;
  41. int t;scanf("%d",&t);
  42. while(t--){
  43. ll ans=0,n,l,r;
  44. scanf("%ld%ld%ld",&n,&l,&r);
  45. ans=combinatorial(n+r-l+1,min(n,r-l+1))-1;
  46. cout<<ans<<endl;
  47. while(ans<0)ans+=mod;
  48. printf("%ld\n",ans%mod);
  49. }
  50. return 0;	
  51. }
  52.  
Success #stdin #stdout 0.01s 3148KB
comments (?)
stdin
copy 
2
1 4 5
2 4 5
stdout
copy 
-1
1000002
-1
1000002
https://ideone.com/iaqmIp
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!