#include <stdio.h>
long long int query(long long int i, long long int j,long long int len, long long int l, long long int r, long long int* val,long long int carry)
{
if(r<0)
{
*val=0;
return 0;
}
if(len==1)
{
if(r==0)
{
*val=1-(carry>0);
return 0;
}
else
{
*val=1-(carry>0);
return 0;
}
}
if(len==2)
{
if(r==0)
{
if(j==0){
*val=0;
return 0;}
else{
if(i==0){
*val=1-(carry>0);
return 0;}
else{
*val=1-(carry>0);
return 0;
}
}
}
else
{
if(j==0){
*val=1;
return 1;}
else{
if(i==0){
if(l<=0){
*val=2-(carry>0);
return 1;}
else{
*val=1-(carry>0);
return 1;
}
}
else{
if(l<=0){
*val=1-(carry>0);
return 0;}
else{
*val=0;
return 0;}
}
}
}
}
if(i==0 && j==len-1)
{
if(r<len-1)
{
if(l>=0)
{
*val=r-l+(carry<=0);
long long int temp= ((r%1000000007)*((r+1)%1000000007)/2-(carry==0?(l%1000000007)*((l-1)%1000000007)/2:(l%1000000007)*((l+1)%1000000007)/2))%1000000007;
return temp>0?temp:1000000007+temp;
}
else
{
*val=r+1;
return ((r%1000000007)*((r+1)%1000000007)/2)%1000000007;
}
}
else
{
if(l>=0)
{
*val=len-l-(carry>0);
long long int temp= ((len%1000000007)*((len-1)%1000000007)/2-(carry==0?(l%1000000007)*((l-1)%1000000007)/2:(l%1000000007)*((l+1)%1000000007)/2))%1000000007;
return temp>0?temp:1000000007+temp;
}
else
{
*val=len;
return ((len%1000000007)*((len-1)%1000000007)/2)%1000000007;
}
}
}
else
{
long long int val2,val1,val0;
val0=0;
val1=0;
val2=0;
long long int sum=0;
long long int len2=len/3;
long long int len1=(len+1)/3;
long long int len0=(len+2)/3;
if(i<len2)
{
if(j<len2)
{
sum+=3*query(i,j,len2,l>1?(l-2)/3:-1,r>1?(r-2)/3:-1,&val2,(l-2)%3+((l-2)%3==0)*carry);
printf("%lld %lld %lld %lld %lld %lld %lld\nsum %lld ",i
,j
,len2
,l
>1?(l
-2)/3:-1,r
>1?(r
-2)/3:-1,val2
,(l
-2)%3+((l
-2)%3==0)*carry
,sum
%1000000007); sum+=2*val2;
printf("sum %lld \n",sum
%1000000007); *val=val2;
}
else if(j<len2+len1)
{
sum+=3*query(i,len2-1,len2,l>1?(l-2)/3:-1,r>1?(r-2)/3:-1,&val2,(l-2)%3+((l-2)%3==0)*carry);
sum+=2*val2;
sum+=3*query(0,j-len2,len1,l>0?(l-1)/3:-1,r>0?(r-1)/3:-1,&val1,(l-1)%3+((l-1)%3==0)*carry);
sum+=val1;
*val=val2+val1;
}
else
{
sum+=3*query(i,len2-1,len2,l>1?(l-2)/3:-1,r>1?(r-2)/3:-1,&val2,(l-2)%3+((l-2)%3==0)*carry);
sum+=2*val2;
sum+=3*query(0,len1-1,len1,l>0?(l-1)/3:-1,r>0?(r-1)/3:-1,&val1,(l-1)%3+((l-1)%3==0)*carry);
sum+=val1;
sum+=3*query(0,j-len2-len1,len0,l/3,r/3,&val0,l%3+(l%3==0)*carry);
*val=val0+val1+val2;
}
}
else if(i<len2+len1)
{
if(j<len2+len1)
{
sum=3*query(i-len2,j-len2,len1,l>0?(l-1)/3:-1,r>0?(r-1)/3:-1,&val1,(l-1)%3+((l-1)%3==0)*carry);
sum+=val1;
*val=val1;
}
else
{
sum=3*query(i-len2,len1-1,len1,l>0?(l-1)/3:-1,r>0?(r-1)/3:-1,&val1,(l-1)%3+((l-1)%3==0)*carry);
sum+=val1;
// printf("%lld ",val1);
sum+=3*query(0,j-len2-len1,len0,l/3,r/3,&val0,l%3+(l%3==0)*carry);
*val=val0+val1;
}
}
else
{
sum=3*query(i-len2-len1,j-len2-len1,len0,l/3,r/3,&val0,l%3+(l%3==0)*carry);
//printf("%lld %lld %lld %lld %lld %lld %lld \n",i-len2-len1,j-len2-len1,len0,l/3,r/3,val0,l%3+(l%3==0)*carry);
*val=val0;
}
return sum;
}
}
int main(void) {
// your code goes here
long long int n,i,j,l,r,val,sum;
int q;
for(int quer=0;quer<q;quer++)
{
scanf("%lld %lld %lld %lld\n",&i
,&j
,&l
,&r
); val=0;
sum=query(i,j,n,l,r,&val,0);
sum=sum%(1000000007);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+Cgpsb25nIGxvbmcgaW50IHF1ZXJ5KGxvbmcgbG9uZyBpbnQgaSwgbG9uZyBsb25nIGludCBqLGxvbmcgbG9uZyBpbnQgbGVuLCBsb25nIGxvbmcgaW50IGwsIGxvbmcgbG9uZyBpbnQgciwgbG9uZyBsb25nIGludCogdmFsLGxvbmcgbG9uZyBpbnQgY2FycnkpCnsKCWlmKHI8MCkKCXsKCQkqdmFsPTA7CgkJcmV0dXJuIDA7Cgl9CglpZihsZW49PTEpCgl7CgkJaWYocj09MCkKCQl7CgkJCSp2YWw9MS0oY2Fycnk+MCk7CgkJCXJldHVybiAwOwoJCX0KCQllbHNlCgkJewoJCQkqdmFsPTEtKGNhcnJ5PjApOwoJCQlyZXR1cm4gMDsKCQl9Cgl9CgkKCWlmKGxlbj09MikKCXsKCQlpZihyPT0wKQoJCXsKCQkJaWYoaj09MCl7CgkJCSp2YWw9MDsKCQkJcmV0dXJuIDA7fQoJCQllbHNlewoJCQkJaWYoaT09MCl7CgkJCQkqdmFsPTEtKGNhcnJ5PjApOwoJCQkJcmV0dXJuIDA7fQoJCQkJZWxzZXsKCQkJCSp2YWw9MS0oY2Fycnk+MCk7CgkJCQlyZXR1cm4gMDsKCQkJfQoJCQl9CgkJfQoJCWVsc2UKCQl7CgkJCWlmKGo9PTApewoJCQkqdmFsPTE7CgkJCXJldHVybiAxO30KCQkJZWxzZXsKCQkJCWlmKGk9PTApewoJCQkJCWlmKGw8PTApewoJCQkJCSp2YWw9Mi0oY2Fycnk+MCk7CgkJCQkJcmV0dXJuIDE7fQoJCQkJCWVsc2V7CgkJCQkJKnZhbD0xLShjYXJyeT4wKTsKCQkJCQlyZXR1cm4gMTsKCQkJCQl9CgkJCQl9CgkJCQllbHNlewoJCQkJCWlmKGw8PTApewoJCQkJCSp2YWw9MS0oY2Fycnk+MCk7CgkJCQkJcmV0dXJuIDA7fQoJCQkJCWVsc2V7CgkJCQkJKnZhbD0wOwoJCQkJCXJldHVybiAwO30KCQkJCX0KCQkJfQoJCX0KCX0KCWlmKGk9PTAgJiYgaj09bGVuLTEpCgl7CgkJaWYocjxsZW4tMSkKCQl7CgkJCWlmKGw+PTApCgkJCXsKCQkJCSp2YWw9ci1sKyhjYXJyeTw9MCk7CgkJCQlsb25nIGxvbmcgaW50IHRlbXA9ICgociUxMDAwMDAwMDA3KSooKHIrMSklMTAwMDAwMDAwNykvMi0oY2Fycnk9PTA/KGwlMTAwMDAwMDAwNykqKChsLTEpJTEwMDAwMDAwMDcpLzI6KGwlMTAwMDAwMDAwNykqKChsKzEpJTEwMDAwMDAwMDcpLzIpKSUxMDAwMDAwMDA3OwoJCQkJcmV0dXJuIHRlbXA+MD90ZW1wOjEwMDAwMDAwMDcrdGVtcDsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCSp2YWw9cisxOwoJCQkJcmV0dXJuICgociUxMDAwMDAwMDA3KSooKHIrMSklMTAwMDAwMDAwNykvMiklMTAwMDAwMDAwNzsKCQkJfQoJCX0KCQllbHNlCgkJewoJCQlpZihsPj0wKQoJCQl7CgkJCQkqdmFsPWxlbi1sLShjYXJyeT4wKTsKCQkJCXByaW50ZigiJWxsZCAiLCp2YWwpOwoJCQkJbG9uZyBsb25nIGludCB0ZW1wPSAoKGxlbiUxMDAwMDAwMDA3KSooKGxlbi0xKSUxMDAwMDAwMDA3KS8yLShjYXJyeT09MD8obCUxMDAwMDAwMDA3KSooKGwtMSklMTAwMDAwMDAwNykvMjoobCUxMDAwMDAwMDA3KSooKGwrMSklMTAwMDAwMDAwNykvMikpJTEwMDAwMDAwMDc7CgkJCQlyZXR1cm4gdGVtcD4wP3RlbXA6MTAwMDAwMDAwNyt0ZW1wOwoJCQl9CgkJCWVsc2UKCQkJewoJCQkJKnZhbD1sZW47CgkJCQlwcmludGYoIiB2YWwgJWxsZCAiLCp2YWwpOwoJCQkJcmV0dXJuICgobGVuJTEwMDAwMDAwMDcpKigobGVuLTEpJTEwMDAwMDAwMDcpLzIpJTEwMDAwMDAwMDc7CgkJCX0KCQl9Cgl9CgllbHNlCgl7CgkJbG9uZyBsb25nIGludCB2YWwyLHZhbDEsdmFsMDsKCQl2YWwwPTA7CgkJdmFsMT0wOwoJCXZhbDI9MDsKCQlsb25nIGxvbmcgaW50IHN1bT0wOwoJCWxvbmcgbG9uZyBpbnQgbGVuMj1sZW4vMzsKCQlsb25nIGxvbmcgaW50IGxlbjE9KGxlbisxKS8zOwoJCWxvbmcgbG9uZyBpbnQgbGVuMD0obGVuKzIpLzM7CgkJaWYoaTxsZW4yKQoJCXsKCQkJaWYoajxsZW4yKQoJCQl7CgkJCQlzdW0rPTMqcXVlcnkoaSxqLGxlbjIsbD4xPyhsLTIpLzM6LTEscj4xPyhyLTIpLzM6LTEsJnZhbDIsKGwtMiklMysoKGwtMiklMz09MCkqY2FycnkpOwoJCQkJcHJpbnRmKCIlbGxkICVsbGQgJWxsZCAlbGxkICVsbGQgJWxsZCAlbGxkXG5zdW0gJWxsZCAiLGksaixsZW4yLGw+MT8obC0yKS8zOi0xLHI+MT8oci0yKS8zOi0xLHZhbDIsKGwtMiklMysoKGwtMiklMz09MCkqY2Fycnksc3VtJTEwMDAwMDAwMDcpOwoJCQkJc3VtKz0yKnZhbDI7CgkJCQlwcmludGYoInN1bSAlbGxkIFxuIixzdW0lMTAwMDAwMDAwNyk7CgkJCQkqdmFsPXZhbDI7CgkJCX0KCQkJZWxzZSBpZihqPGxlbjIrbGVuMSkKCQkJewoJCQkJc3VtKz0zKnF1ZXJ5KGksbGVuMi0xLGxlbjIsbD4xPyhsLTIpLzM6LTEscj4xPyhyLTIpLzM6LTEsJnZhbDIsKGwtMiklMysoKGwtMiklMz09MCkqY2FycnkpOwoJCQkJc3VtKz0yKnZhbDI7CgkJCQlzdW0rPTMqcXVlcnkoMCxqLWxlbjIsbGVuMSxsPjA/KGwtMSkvMzotMSxyPjA/KHItMSkvMzotMSwmdmFsMSwobC0xKSUzKygobC0xKSUzPT0wKSpjYXJyeSk7CgkJCQlzdW0rPXZhbDE7CgkJCQkqdmFsPXZhbDIrdmFsMTsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCXN1bSs9MypxdWVyeShpLGxlbjItMSxsZW4yLGw+MT8obC0yKS8zOi0xLHI+MT8oci0yKS8zOi0xLCZ2YWwyLChsLTIpJTMrKChsLTIpJTM9PTApKmNhcnJ5KTsKCQkJCXN1bSs9Mip2YWwyOwoJCQkJc3VtKz0zKnF1ZXJ5KDAsbGVuMS0xLGxlbjEsbD4wPyhsLTEpLzM6LTEscj4wPyhyLTEpLzM6LTEsJnZhbDEsKGwtMSklMysoKGwtMSklMz09MCkqY2FycnkpOwoJCQkJc3VtKz12YWwxOwoJCQkJc3VtKz0zKnF1ZXJ5KDAsai1sZW4yLWxlbjEsbGVuMCxsLzMsci8zLCZ2YWwwLGwlMysobCUzPT0wKSpjYXJyeSk7CgkJCQkqdmFsPXZhbDArdmFsMSt2YWwyOwoJCQl9CgkJfQoJCWVsc2UgaWYoaTxsZW4yK2xlbjEpCgkJewoJCQlpZihqPGxlbjIrbGVuMSkKCQkJewoJCQkJc3VtPTMqcXVlcnkoaS1sZW4yLGotbGVuMixsZW4xLGw+MD8obC0xKS8zOi0xLHI+MD8oci0xKS8zOi0xLCZ2YWwxLChsLTEpJTMrKChsLTEpJTM9PTApKmNhcnJ5KTsKCQkJCXN1bSs9dmFsMTsKCQkJCSp2YWw9dmFsMTsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCXN1bT0zKnF1ZXJ5KGktbGVuMixsZW4xLTEsbGVuMSxsPjA/KGwtMSkvMzotMSxyPjA/KHItMSkvMzotMSwmdmFsMSwobC0xKSUzKygobC0xKSUzPT0wKSpjYXJyeSk7CgkJCQlzdW0rPXZhbDE7CgkJCS8vCXByaW50ZigiJWxsZCAiLHZhbDEpOwoJCQkJc3VtKz0zKnF1ZXJ5KDAsai1sZW4yLWxlbjEsbGVuMCxsLzMsci8zLCZ2YWwwLGwlMysobCUzPT0wKSpjYXJyeSk7CgkJCQkqdmFsPXZhbDArdmFsMTsKCQkJfQoJCX0KCQllbHNlCgkJewoJCQlzdW09MypxdWVyeShpLWxlbjItbGVuMSxqLWxlbjItbGVuMSxsZW4wLGwvMyxyLzMsJnZhbDAsbCUzKyhsJTM9PTApKmNhcnJ5KTsKCQkJLy9wcmludGYoIiVsbGQgJWxsZCAlbGxkICVsbGQgJWxsZCAlbGxkICVsbGQgXG4iLGktbGVuMi1sZW4xLGotbGVuMi1sZW4xLGxlbjAsbC8zLHIvMyx2YWwwLGwlMysobCUzPT0wKSpjYXJyeSk7CgkJCSp2YWw9dmFsMDsKCQl9CgkJcmV0dXJuIHN1bTsKCX0KfQppbnQgbWFpbih2b2lkKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglsb25nIGxvbmcgaW50IG4saSxqLGwscix2YWwsc3VtOwoJc2NhbmYoIiVsbGRcbiIsJm4pOwoJaW50IHE7CglzY2FuZigiJWRcbiIsJnEpOwoJZm9yKGludCBxdWVyPTA7cXVlcjxxO3F1ZXIrKykKCXsKCQlzY2FuZigiJWxsZCAlbGxkICVsbGQgJWxsZFxuIiwmaSwmaiwmbCwmcik7CgkJdmFsPTA7CgkJc3VtPXF1ZXJ5KGksaixuLGwsciwmdmFsLDApOwoJCXN1bT1zdW0lKDEwMDAwMDAwMDcpOwoJCXByaW50ZigiJWxsZFxuIixzdW0pOwoJfQoJcmV0dXJuIDA7Cn0K