Description：

多次询问： $$ S_{n,m}={n\choose m} $$ $1\leqslant n\leqslant 10^5$

Solution：

首先组合数有公式： $$ S_{n+1,m}=S_{n,m}\times 2-{n\choose m} $$ 给杨辉三角每一行每隔 $\sqrt n$ 标一个点，共 $n\sqrt n$ 个点，用上面那个公式预处理出所有这些点的位置的值。

询问时先获得上一个标点的位置的值，然后预处理阶乘及其逆元 $O(1)$ 求组合数，暴力边上那些不足 $\sqrt n$ 的部分，时间复杂度 $O(n\sqrt n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

#define BLOCK 400

#define MAXN 100010

int sum[MAXN][BLOCK];

#define MOD 1000000007

int fac[MAXN],inv[MAXN];

typedef long long ll;

inline int power(int a,int b)

{

	register int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

inline int C(int n,int m)

{

	if(n < m)return 0;

	return 1ll * fac[n] * inv[m] % MOD * (ll)inv[n - m] % MOD;

}

inline void init()

{

	fac[0] = 1;for(register int i = 1;i < MAXN;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[0] = 1;inv[MAXN - 1] = power(fac[MAXN - 1],MOD - 2);

	for(register int i = MAXN - 2;i >= 1;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	for(register int i = 0;i * BLOCK < MAXN;++i)sum[0][i] = 1;

	for(register int i = 1;i < MAXN;++i)

		for(register int j = 0;j * BLOCK < MAXN;++j)

			sum[i][j] = (sum[i - 1][j] * 2 % MOD - C(i - 1,j * BLOCK) + MOD) % MOD;

	return;

}

inline void work()

{

	register int n,m;

	n = read();m = read();

	register int p = m / BLOCK;

	register int res = sum[n][p];

	p = p * BLOCK + 1;

	for(register int i = p;i <= m;++i)res = (res + C(n,i)) % MOD;

	printf("%d\n",res);

	return;

}

int main()

{

	freopen("sum.in","r",stdin);

	freopen("sum.out","w",stdout);

	init();

	int id,testcases;

	scanf("%d%d",&id,&testcases);

	while(testcases--)work();

	fclose(stdin);

	fclose(stdout);

	return 0;

}