假设从 $(X_0, Y_0)$ 经过 x 次第一种方式和 y 次第二种方式，可以到达 $(X_1, Y_1)$。

则可以列出方程组：

$X_0+ax+cy=X_1$①

$Y_0+bx+dy=Y_1$②

可以发现，从一个点移动到另一个点，x, y 是唯一的，即步数是确定的。

原先的问题转化成了一个很套路的坐标系上走路问题：

从 (0,0) 出发，每次只能向上或向右走一个单位，求到达终点的方案数。

本题加上了坏点，则可以使用容斥。

原点视为第 0 个坏点，目标点视为第 n+1 个坏点。

设 f(i) 为到达第 i 个坏点且不经过之前任意坏点的方案数，则答案就是 f(n+1)。

现在，要考虑如何求 f(i)。

于是就想到了容斥。

既然要不经过之前任意坏点，我们就求出经过之前若干坏点的非法方案数，然后用总方案数减去非法方案数就是合法方案数。

则，如何求出非法方案数呢？

考虑既然经过了坏点，且坏点又是有序的，我们可以枚举之前经过的第一个坏点 j。

那么，在到达 j 之前，不能经过任何障碍点；从 j 与到达 i 之间，可以任意走。

如果定义一个函数 cnt(u,v) 表示从第 u 个坏点到第 v 个坏点的方案数，那么就有转移方程：

$f(i)=cnt(0,i)-\sum_{j=1}^{i-1}f(j)· tot(j,i)$

而 cnt(u,v) 呢，实际上可以用组合数直接计算，就是 $C_{x_v-x_u+y_v-y_u}^{x_v-x_u}$。

于是这道题就做完了。