1
const int MAXN = 1e7;
2
const int MOD = 1e9 + 7;
3

4
vector<int> fact(MAXN), invfact(MAXN);
5
bool inited = 0;
6
int ksm(int base, int exp)
7
{
8
  int ans = 1;
9
  while (exp)
10
  {
11
    if (exp & 1)
12
    {
13
      ans = ans * base % MOD;
14
    }
15
    base = base * base % MOD;
16
    exp >>= 1;
17
  }
18
  return ans;
19
}
20

21
int inv(int x)
22
{
23
  return ksm(x, MOD - 2);
24
}
25

26
void pre()
27
{
28
  if (inited) return;
29
  inited = 1;
30
  fact[0] = 1;
31
  for (int i = 1; i < MAXN; i++)
32
  {
33
    fact[i] = fact[i - 1] * i % MOD;
34
  }
35

36
  invfact[MAXN - 1] = inv(fact[MAXN - 1]);
37
  for (int i = MAXN - 2; i >= 0; i--)
38
  {
39
    invfact[i] = invfact[i + 1] * (i + 1) % MOD;
40
  }
41
}
42

43
int comb(int n, int k)
44
{
45
  if (!inited)
46
    {
47
        pre();
48
  }
49

50
  if (k < 0 or k > n)
51
    {
52
        return 0;
53
    }
54

55
  return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
56
}