出现的问题
计算组合数（公式如下）时，
$$ C_{n}^{m}=\frac{n!}{m!\times(n-m)!} $$
如果n很大，一般会要求将结果对某个数（比如 $1e9$ ）取模，显然 $n!$ 会非常大，可能 long long 都存不下，所以要一边乘，一边取模。数论中有三个式子
$$ (a + b) % p = (a % p + b % p)%p $$
$$ (a - b) % p = (a % p - b % p) % p $$
$$ (a * b) % p = ((a % p) \times (b % p)) % p $$
但是对于除法却不成立，所以需要用逆元来解决
简介
若$a \times x % M = 1$，我们就称$x$是$a$的逆元，$x$可以写作$a^{-1}$次方（相当于整除中的倒数)
用途
假设我们需要求$a \div b % M$的值，而由于上述种种原因，我们不能直接除，这时就可以对式子进行一些操作:
$$ a \div b % M = a \div b \times 1 % M = a \div b \times (b \times b^{-1}) % M = a \times b^{-1} % M $$
注意：
- 上式中的$b$的$-1$次方指的是b的逆元
- 第三步变形的依据是：$b \times b^{-1} % M = 1$（这是第一行的定义）
现在就已经把除法转换为了乘法，可以正常计算了
怎么求逆元
怎么求一个数的逆元呢？
首先，要求一个数的逆元，需要两个元素，这个数（$a$）和模数（$M$）
$$ a \times a^{-1} % M = 1 $$
根据费马小定理（$a^{p - 1} \equiv 1\pmod p$）可得（$M$须为质数）：
$$ a^{-1} = a^{M - 2}（这里要用到快速幂） $$
可以求逆元了，那怎么求阶乘的逆元呢？
可以根据性质$inv[i] = (M - M \div i) \times inv[M % i] % M(inv[1] = 1)$顺着求出每个数的逆元然后再把每个数的inv乘起来，得到阶乘的逆元
可以从后往前推：
若$n!$的逆元 $= k$ 即$n! \times k % M = 1$ 因为$n - 1! = n! \div n$， $n! \div n \times k \times n % M = 1$ 所以$(n - 1)!$的逆元等于$k \times n$，
可以先正推求出$fac[i]$（$i$的阶乘），再通过费马小定理算出$inv[n]$（和上面不同，这里是指$n!$的逆元），最后倒推求出所有的$inv[i]$