# COUNT SEQUENCE -WA

#include<stdio.h>
#define M 1000003

int main(){

``````  int t=0;
long long int sum=0,L,R,N,init=0,i=0,Len=0;
scanf("%d",&t);
while(t-- > 0){
scanf("%lld%lld%lld",&N,&L,&R);

Len=R-L+1;

if(R==L){

printf("%lld\n",N%M);
}
else{
init=Len%M;

sum=init;
if(N>Len)
N=Len%M;
for(i=2;i<=N;i++){

init=((((init%M)*(((Len%M)+(i%M)-(1%M))%M))%M)/(i%M))%M;

//printf("%lld",init);
sum=(sum%M+init%M)%M;
}

printf("%lld\n",sum);
sum=0;
}

}
//getch();
return 0;
``````

}

I HAVE USED THE FORMULA (R-L+r,r) where 1<=r<=N.
I have broken the the aboe using (n+1,k)=(n,k)+(n,k-1);
WHAT wrong In My code??

Hi, I’m not 100% sure, but I think the division is your problem. When you are working with modulo operation, the division is not working the way you think.

For example: (10^6+4) / 2 == 5*10^5 + 2, but ((10^6+4)%M) / (2%M) == 1 / 2 == 0

I think you should check the Modulat Multiplicative Inverse or Fermat’s Little Theorem.

Perhaps yours formula is wrong.

Correct one is

Summation of (Leng+r-1,r) over r where r varies from 1 to N.

Leng=R-L+1.

This will give you tle as you will iterate over each r.

So you can convert this into non iterative.

Ans is (leng+N,N)-1.

Where leng =r-l+1.
and N is given length of sequence.
You can solve it using Lucas.