T1
原来组合数有通项公式（大雾）
线性求逆元：
显然，\(1^{-1}\equiv 1(\operatorname{mod} p)\)
令 \(k=\lfloor \frac{p}{i} \rfloor,j=p\operatorname{mod}i\)，则 \(p=i\times k+j\)
则 \(0\equiv i\times k+j (\operatorname{mod} p)\)
两边同时乘 \(i^{-1}\times j^{-1}\)
得 \(0\equiv k\times j^{-1}+i^{-1}(\operatorname{mod} p)\)
移项得 \(i^{-1}\equiv -k\times j^{-1}(\operatorname{mod} p)\)
代入得 \(i^{-1}\equiv \lfloor \frac{p}{i} \rfloor \times j^{-1}\)
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (p - p / i) * inv[p % i] % p;
}
考虑逆元的意义为模意义下倒数，则 \(fac_i^{-1}\equiv fac_{i+1}^{-1}\times (i+1)(\operatorname{mod} p)\)
T2
扫描线，二位数点