本文发表于 239 天前，其中的信息可能已经事过境迁
AT_tenka1_2014_final_d
提供不需要莫队的做法。
我们知道组合数
考虑这个是怎么得到的呢，你就画一段区间，你去对区间每一个点加上其贡献方便得到。
然后？然后做完了。
取定块长
顺序做
总时间复杂度
cpp
void __INIT__(long long n);
#include<bits/stdc++.h>
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;i++)
#define drep(i,a,b) for(reg int i=a;i>=b;i--)
#define ll long long
#define int long long
using namespace std;
const int N=2000003,mod=1e9+7;
struct R{
int n,k,id;
bool operator < (const R x)const {
return n<x.n;
}
}r[N];
int L[N],R[N],val[N],sz;
ll fac[N+50],inv[N+50];
ll qpow(ll a,ll b){ll ans=1,tmp=a;while(b){if(b&1)ans=ans*tmp%mod;tmp=tmp*tmp%mod;b>>=1;}return ans;}
ll C(ll n,ll m){ return fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll lucas(ll n,ll m){
if(n<mod&&m<mod){
if(n<m)return 0;
return C(n,m);
}
return lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;
}
int B=316,ans[N];
int rev(int x){
return (x-1)/B+1;
}
signed main(){
__INIT__(2000002);
int m;cin>>m;for(int i=1;i<=m;i++){cin>>r[i].n>>r[i].k;r[i].id=i;}
sort(r+1,r+m+1);
int it=1;
for(int i=1;i<=100001;i++){
int now=(i-1)/B+1;
if(!L[now])L[now]=i;
R[now]=i;
sz=max(sz,now);
}
val[0]=1,val[1]=1;
for(int i=1;i<=m;i++){
while(it<r[i].n){
for(int now=1;now<=sz;now++){
val[now]=(val[now]+val[now]-lucas(it,R[now])+lucas(it,L[now]-1)+mod)%mod;
}
it++;
}
int res=1;
int myr=rev(r[i].k);
if(R[myr]!=r[i].k){
for(int j=L[myr];j<=r[i].k;j++)(res+=lucas(it,j))%=mod;
myr--;
}
for(int j=1;j<=myr;j++)(res+=val[j])%=mod;
ans[r[i].id]=res;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}
void __INIT__(int n){
fac[1]=1,fac[0]=1;
rep(i,2,n)fac[i]=(i*fac[i-1])%mod;
ll res=inv[n]=qpow(fac[n],mod-2);
drep(i,n-1,0)inv[i]=((res*=(i+1))%=mod);
inv[0]=1;
return void();
}