分析

• 这一题如果仍然使用递推的方式求解的话，因为$1 \le b \le a \le 10^5$，计算量最大为$10 ^ 10$，大约十亿的复杂度，完全不能被接受。

• 这一题需要使用到的公式是：

$$ C_a^b = \frac{a!}{b! \times (a-b)!} $$

• 存在的问题是阶乘太大，计算机无法存储下来，另外我们最终的结果需要对$10^9+7$取模，因此考虑值存取取模后的结果，但是遗憾的是：

$$ \frac{a}{b} \ (mod \ p) \neq \frac{a \ (mod \ p)}{b \ (mod \ p)} $$

• 那该怎么办呢？这里就要使用到了逆元，关于逆元可以参考：网址。

• $\frac{a}{b} \equiv a \times x \ (mod \ m)$，我们求出分母的逆元即可，因为p是质数，所以任何数都与p互质，因此逆元存在，另外由于p是质数，可以使用快速幂求解逆元。

• 另外根据逆元定义很容易验证b、c的逆元相乘的结果等于$b \times c$的逆元。

• 实际代码中我们可以使用数组fact记录各个数据阶乘的结果，数组infact记录阶乘对应的逆元，最终

$$ C_a^b = ((fact[a] \times infact[b]) \% p) \times infact[a-b]) \% p $$

• 计算量：预处理各个数的阶乘以及阶乘的逆元，求逆元可以使用快速幂，因此时间复杂度为$O(n\times log(n))$，计算量为$10^5 \times log(10^5) \approx 1.6 \times 10 ^ 6$。可以接受。

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int fact[N];  // fact[i]存储 (i!)%mod 的结果
int infact[N];  // infact[i]存储 (i!模mod的逆元)%mod 的结果

int qmi(int a, int b, int p) {

    int res = 1 % p;
    while (b) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {

    fact[0] = infact[0] = 1;  // 0!=1, 1的逆元是1
    for (int i = 1; i < N; i++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }

    int n;
    scanf("%d", &n);
    while (n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }

    return 0;
}