用 ext_gcd 实现的组合数工具，可以使用 init_tool 初始化范围与模数，使用 C （组合）或 A （排列）函数时请务必保证参数 和 均小于初始化的范围，参数 与初始化的模数相等。
/*******************************************
* Code Info
Author: xvl_
Date: 2023.10.20
* Problem Info
Online Judge: Unknown
Url: Unknown
*******************************************/
#include <bits/stdc++.h>
namespace xvl_ {
#define ll long long
#define ld long double
#define IMAX 1e9
#define LMAX 1e18
#define SP(n, x) std :: setprecision(n) << std :: fixed << x
#define Off_Sync ios :: sync_with_stdio(0); cin.tie(0)
void debug() { std :: cerr << "debug" << "\n"; }
template <typename T> inline T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> inline T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
template <typename T> inline T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> inline T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
namespace Tool {
std :: vector <ll> fac;
std :: vector <ll> invf;
void ext_gcd(ll a, ll b, ll& d, ll&x, ll&y) {
if (!b) d = a, x = 1, y = 0;
else {
ext_gcd(b, a % b, d, y, x);
y -= a / b * x;
}
}
void init_tool(int n, int p) {
fac.resize(n + 1);
invf.resize(n + 1);
ll d(0), x(0), y(0);
fac[0] = 1;
for (int i(1); i <= n; i++) fac[i] = fac[i - 1] * i % p;
ext_gcd(fac[n], p, d, x, y);
invf[n] = (x + p) % p;
for (int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % p;
}
ll C(int n, int m, int p) { if (n < 0 or m < 0 or m > n) return 0; return fac[n] * invf[m] % p * invf[n - m] % p; }
ll A(int n, int m, int p) { if (n < 0 or m < 0 or m > n) return 0; return fac[n] * invf[n - m] % p; }
}
using namespace std;
using namespace xvl_;
using namespace Tool;
int T;
int main() {
// freopen("InName.in", "r", stdin);
// freopen("OutName.out", "w", stdout);
Off_Sync;
init_tool(10000000, 1000000007);
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
cout << C(n, k, 1000000007) << "\n";
}
return 0;
}