题意：

给出n，m，求$C_n^1+C_n^2+···+C_n^m$，答案模$10^9+7$。

其中$1≤T≤10^5$，$1≤m≤n≤10^5$。

思路：

比赛的时候我是根据dp，想到这相当于是杨辉三角的前缀和，画出这个三角之后感觉是个莫队啊？然而觉得转移有点麻烦没细想而且队友打表打出的另一道题目有点东西就去转战其他题目了…赛后看题解感觉血亏啊？

m的转移相当于$S(n,m)=S(n,m-1)+C_n^m$，就是前缀和的递推。

n的转移相当于$S(n,m)=2*S(n-1,m)-C_{n-1}^m$（zz如我…很好推的我怎么还想了这么久？？？）。

$S(n,m)=\sum_{i=0}^{m-1} C_{n-1}^k+\sum_{i=0}^{m} C_{n-1}^k=2*S(n-1,m)-C_{n-1}^m$。

然后莫队一下就可以了。

注意组合数的处理用线性求出阶乘的逆元的方法比较好。

交上去AC之后发现自己写的就是比别人跑得慢啊？以为自己写的程序自带常数了啊？？？其实是模得太多了啊？两个式子可以合并就尽量写一个 模能不用就不用 很慢的啊。

代码：

typedef long long ll;
void read(int &x)
{
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
}
void write(ll x){
    if(x==0){putchar(48);return;}
    int len=0,dg[20];
    while(x>0){dg[++len]=x%10;x/=10;}
    for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
struct qnode
{
    int l,r,id;
}q[100010];
ll fac[100010];
ll inv[100010];
ll tot;
ll ans[100010];
int pos[100010];
bool cmp(qnode x,qnode y)
{
    if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
    return x.r<y.r;
}
long long PowerMod(long long a,long long b,long long c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
            ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<=MAXN;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[MAXN]=PowerMod(fac[MAXN],MOD-2,MOD);
    for(int i=MAXN-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
}
ll calc(int n,int m)
{
    if(n<m)return 0;
    return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
    int m;
    read(m);
    init();
    int block=sqrt(MAXN);
    for(int i=1;i<=m;i++)
    {
        read(q[i].l);read(q[i].r);
        q[i].id=i;
        pos[i]=(i-1)/block;
    }
    sort(q+1,q+1+m,cmp);
    int L=0,R=0;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        while(L>q[i].l)
        {
            L--;
            tot=(tot+calc(L,R))*xs%MOD;
        }
        while(L<q[i].l)
        {
            tot=(tot*2-calc(L,R)+MOD)%MOD;
            L++;
        }
        while(R<q[i].r)
        {
            R++;
            tot=(tot+calc(L,R))%MOD;
        }
        while(R>q[i].r)
        {
            tot=(tot-calc(L,R)+MOD)%MOD;
            R--;
        }
        ans[q[i].id]=tot;
    }
    for(int i=1;i<=m;i++)
    {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}