有一个递推式：

$s(n+1,m)=(s(n,m)-C_n^m)\times 2+C_n^m$

$s(n,m+1)=s(n,m)+C_n^{m+1}$

萌新刚学莫队，求问可不可以使用莫队，如果可以，莫队是不是该这么写/kk

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007ll
#define N 100005
int fac[N],inv[N],ans[N];
int t,i,j,k,s,bk,now;
struct query
{
	int l,r,id;
	bool operator<(const query &x)const
	{
  		if(l/bk!=x.l/bk) return l<x.l;
		return (l/bk)&1 ? r<x.r:r>x.r;
	}
} a[N];
int qm_n(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		b>>=1;a=a*a%mod;
	}
	return ans%mod;
}
int C(int n,int m)
{
	if(n<m)return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
	fac[0]=1;
	for(i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	inv[N-1]=qm_n(fac[N-1],mod-2);
	for(i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	scanf("%lld",&t);bk=sqrt(N);
	for(i=1;i<=t;i++) scanf("%lld %lld",&a[i].r,&a[i].l),a[i].id=i;
	sort(a+1,a+t+1);
	k=1;s=0;
	//k:m s:n
	//l:m r:n
	for(i=1;i<=t;i++)
	{
		if(a[i].l==a[i].r)
		{ans[a[i].id]=1;continue;
		}
		while(k>a[i].l) now=(now-C(k,s)+mod)%mod,k--;
		while(s<a[i].r) now=(((now-C(k,s)+mod)+mod)*2%mod+C(k,s))%mod,s++;
		while(k<a[i].l) k++,now=(now+C(k,s))%mod;
		while(s>a[i].r) s--,now=((now-C(k,s)+mod)%mod*500000004ll%mod+C(k,s))%mod;
		ans[a[i].id]=now;
	}
	for(i=1;i<=t;i++) printf("%lld\n",ans[i]);
	return 0;
}