组合数C

$$C_n ^ m = \frac{n!}{m!(n - m)!}$$

枚举一条路径第一次碰到的障碍，求出这些方案数，从总方案数减去即可。

$$\text{Ans}=\operatorname{C}_{n+m-2}^{n-1}-\sum_{i=1}^kf_i\operatorname{C}_{n+m-x_i-y_i}^{n-x_i} ​$$

f i表示到达第 i 个障碍的方案数。 求解 f i ​ 考虑容斥，是类似 Ans 的求解的:

$$f_i=\operatorname{C}_{x_i+y_i-2}^{x_i-1}-\sum_{x_j\leq x_i,y_j\leq y_i}f_j\operatorname{C}_{x_i+y_i-x_j-y_j}^{x_i-x_j}$$

long long C(int x, int y)
{return fac[y]*finv[x]% mod*finv[y- x]% mod;
}