# Basics of Factorization And Combinatorics

```// Usage:
//      Math ma;
//      ma.prepare(n);
//      usage ma.getA(n, k), ma.fac[i], ma.twop[i], ma.iv_twop[i]
struct Math
{
int n;
int MOD;
int SMALL_N;

ll *r;
ll *fac, *ifac;
ll **A, **C;
ll *twop, *iv_twop;

Math() {
n = -1;
MOD = 1;
SMALL_N = 3030;
}

void prepare(int n_, int MOD_) {
n = n_;
MOD = MOD_;

// inverse modulo of 1 -> n (% MOD). Assume n < m.
r = new ll[n+1];
r[1] = 1;
for (int i = 2; i <= n; ++i)
r[i] = (MOD - (MOD/i) * r[MOD%i] % MOD) % MOD;

// factorial and its inverse modulo
fac = new ll[n+1];
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i-1] * i % MOD;

ifac = new ll[n+1];
ifac[0] = ifac[1] = 1;
for (int i = 2; i <= n; ++i)
ifac[i] = ifac[i-1] * r[i] % MOD;

// 2^ and its inverse
twop = new ll[n+1];
iv_twop = new ll[n+1];

twop[0] = iv_twop[0] = 1;
twop[1] = 2; iv_twop[1] = (MOD+1)/2; // This is True when MOD is odd
for (int i = 2; i <= n; ++i) {
twop[i] = twop[i-1] * 2 % MOD;
iv_twop[i] = iv_twop[i-1] * iv_twop[1] % MOD;
}

// A
if (n <= SMALL_N) {
A = new ll*[n+1];
for (int i = 0; i <= n; ++i) {
A[i] = new ll[n+1];
fill(A[i], A[i] + n + 1, 0);
}

for (int i = 0; i <= n; ++i)
A[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
A[i][j] = A[i][j-1] * (i-j+1) % MOD;
}

// C
if (n <= SMALL_N) {
C = new ll*[n+1];
for (int i = 0; i <= n; ++i) {
C[i] = new ll[n+1];
fill(C[i], C[i] + n + 1, 0);
}

for (int i = 0; i <= n; ++i)
C[i][0] = C[i][i] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}

}

ll getA(int n_, int k_) {
if (k_ < 0 || n_ < 0)
return 0;

if (n_ <= n && n <= SMALL_N)
return A[n_][k_];

return fac[n_] * ifac[n_ - k_] % MOD;

}

ll getC(int n_, int k_) {
if (k_ < 0 || n_ < 0)
return 0;

if (n_ <= n && n <= SMALL_N)
return C[n_][k_];

return fac[n_] * ifac[n_ - k_] % MOD * ifac[k_] % MOD;

}

};
```