<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Binomial Coefficients

## Description
Your task is to calculate $n$ binomial coefficients modulo $10^9+7$.
A binomial coefficient $a \choose b$ can be calculated using the formula $\frac{a!}{b!(a-b)!}$. We assume that $a$ and $b$ are integers and $0≤b≤a$.
## Input
The first input line contains an integer $n$: the number of calculations.
After this, there are $n$ lines, each of which contains two integers $a$ and $b$.
$1≤n≤10^5$
$0≤b≤a≤10^6$

## Output
Print each binomial coefficient modulo $10^9+7$.

## 解題思路
建表儲存各階層的數值和乘法反元素，再計算即可

### 時間複雜度
取反元素 $O(lg\ a)$
總時間複雜度 $O(n\ lg\ a)$

## Code

#include <iostream>
#include <utility>

const int MOD = 1'000'000'007;

std::pair<long long int, long long int> extgcd(long long int a, long long int b) {
    if (b == 0) return {1, 0};
    auto [xp, yp] = extgcd(b, a % b);
    return {yp, xp - a / b * yp};
}

long long int factorial[1000000] = {1};
long long int inverse[1000000] = {1};
int main() {
    for (int i = 1; i <= 1000000; i++) {
        factorial[i] = factorial[i - 1] * i % MOD;
        inverse[i] = extgcd(factorial[i], MOD).first;
        // std::cout << factorial[i] << ',' << inverse[i] << std::endl;
    }
    int testcase;
    std::cin >> testcase;
    while (testcase--) {
        int a, b;
        std::cin >> a >> b;
        std::cout << (factorial[a] * inverse[b] % MOD * inverse[a - b] % MOD + MOD) % MOD << std::endl;
    }
    return 0;
}