[csp-s 模拟2] 线段树

#include<bits/stdc++.h>
#define lcs (rt<<1)
#define rcs (rt<<1|1)
#define axe r-l+1
using namespace std;
using ll=long long;
const int mod=1e9+7;
ll T,n,x,y;map<ll,ll> k,b;
void dfs(ll n){
	if(k[n]) return;
	ll n1=ceil(1.0*n/2);dfs(n1);
	ll n2=floor(1.0*n/2);dfs(n2);
	k[n]=((k[n1]+k[n2])<<1|1)%mod;
	b[n]=(b[n1]+b[n2]+k[n2])%mod;
}
int query(int rt,ll l,ll r,ll L,ll R){
	if(L>r||R<l) return 0;
	if(L<=l&&r<=R) return dfs(axe),(k[axe]*rt+b[axe])%mod;
	ll mid=(l+r)>>1;
	return (query(lcs%mod,l,mid,L,R)+query(rcs%mod,mid+1,r,L,R))%mod;
}
int main(){
	scanf("%lld",&T);k[1]=1;
	while(T--){
		scanf("%lld%lld%lld",&n,&x,&y);
		printf("%d\n",query(1,1,n,x,y));
	}
	return 0;
}