题意重述

从 $(0,0)$ 出发，恰好 $R$ 步跳到 $(T_x, T_y)$。
每一步：

• 只能向右上跳：新位置 $(\text{newx},\text{newy})$ 满足 $x \le \text{newx} \le x+M_x$，$y \le \text{newy} \le y+M_y$。
• 不能原地不动（排除 $(0,0)$ 增量）。
• 有 $K$ 个非法向量 $(k_i,k_i)$，即每一步的横向增量 $dx$ 和纵向增量 $dy$ 不能 同时等于 $k_i$（也就是不能沿对角线走长度为 $k_i$ 的向量）。

已知 $k_i$ 都是 $G$ 的倍数，$10000 \le G \le 50000$。

求方案数，对 $10^9+7$ 取模。

---

第一步：基本思路

这是一个 多步二维路径计数 问题，需要走 $R$ 步，每步 $dx,dy$ 非负且不同时为零，且 $dx \le M_x$，$dy \le M_y$，还要避开 $K$ 个非法对角线增量。

设第 $t$ 步的增量为 $(dx_t, dy_t)$，则：

$$\sum_{t=1}^R dx_t = T_x, \quad \sum_{t=1}^R dy_t = T_y. $$

且对每个 $t$：$0 \le dx_t \le M_x$，$0 \le dy_t \le M_y$，$(dx_t, dy_t) \neq (0,0)$，$(dx_t, dy_t) \neq (k_i,k_i)$ 对任何 $i$。

---

第二步：转化为生成函数

由于每一步独立（除了最后总和限制），可以用生成函数。

对于一步，合法增量集合 $S$ 定义为：

$$S = \{ (a,b) \mid 0 \le a \le M_x, \ 0 \le b \le M_y, \ (a,b) \neq (0,0), \ (a,b) \notin \{ (k_i,k_i) \}_{i=1}^K \}. $$

则一步的生成函数为：

$$F(x,y) = \sum_{(a,b) \in S} x^a y^b.$$

走 $R$ 步的生成函数为 $F(x,y)^R$，我们要求其中 $x^{T_x} y^{T_y}$ 的系数。

---

第三步：利用 $k_i$ 是 $G$ 的倍数

$G$ 很大（$10^4 \sim 5\times 10^4$），而 $T_x,T_y \le 10^6$，$M_x,M_y \le 10^6$，非法向量只出现在对角线且步长是 $G$ 的倍数。

这意味着 非法向量很稀疏（对角线上的 $dx=dy$ 且为 $G$ 的倍数）。

我们可以在计数时先考虑所有合法向量（包括所有非对角线和对角线非法的排除），再减掉非法对角线向量。

---

第四步：直接二维生成函数的问题

二维生成函数幂的系数提取复杂度高，但这里 $R \le 1000$，$T_x,T_y$ 很大，直接二维卷积不可行。

由于 $dx,dy$ 独立？不独立，因为有非法对角线限制。
但我们可以换个角度：
令 $u_t = dx_t - dy_t$，$v_t = dx_t$，这样 $(dx,dy) = (v, v-u)$？不，这样不方便。
不如直接对 $dx,dy$ 分别考虑，最后合起来。

---

关键想法：用容斥处理非法对角线

非法向量是 $(k_i,k_i)$，即 $dx=dy=k_i$。
如果我们忽略非法限制，一步生成函数是：

$$F_0(x,y) = \sum_{a=0}^{M_x} \sum_{b=0}^{M_y} x^a y^b - 1 \quad\text{(减去(0,0))}. $$

即：

$$F_0(x,y) = \frac{(1-x^{M_x+1})(1-y^{M_y+1})}{(1-x)(1-y)} - 1. $$

非法向量集合是 $B = \{(k_i,k_i) \mid i=1..K\}$（去重后）。
设 $B = \{g_1, g_2, \dots, g_m\}$，其中 $g_j$ 是 $G$ 的倍数，且 $g_j \le \min(M_x,M_y)$。

容斥原理：合法方案 = 总方案 - 至少用一次非法向量的方案 + 至少用两次非法向量的方案 - ……

设 $A_j$ 表示“某一步用了非法向量 $(g_j,g_j)$”，我们要计算：

$$\sum_{S \subseteq \{1,\dots,m\}} (-1)^{|S|} \times (\text{所有步都可用任何向量，但必须包含 $S$ 中每个非法向量至少一次，且总步数 $R$，总增量 $(T_x,T_y)$})。 $$

---

第五步：容斥后的计数

如果固定一个非法向量集合 $S$，设 $S$ 中元素（不同的 $g_j$）的集合为 $\{h_1, \dots, h_t\}$。
我们必须保证这 $t$ 个非法向量每个至少出现一次，其它步任意（包括可再用这些非法向量，因为容斥已经处理了符号）。

这相当于：
我们先分配 $t$ 步，每步强制为 $(h_s, h_s)$（对每个 $s$ 至少一步），总步数 $R$，其余 $R-t$ 步从 $F_0(x,y)$ 中任选（可包含非法向量，因为这里已经固定了至少出现一次，其它步随意）。

这里 $t \le |S|$，但注意 $S$ 是原 $K$ 个可能重复的非法向量的一个子集，容斥是按 $K$ 个非法向量（编号）做的，所以 $|S|$ 可能大于不同 $g_j$ 的数量，但 $g_j$ 相同时，它们对应的非法向量相同，容斥时要小心。

实际上更简单：
设非法向量有 $m$ 种不同的值 $d_1,\dots,d_m$，每种出现了 $c_j$ 次（输入可能重复）。

容斥时，我们枚举 $t_j$ 表示第 $j$ 种非法向量被禁用的次数（$0 \le t_j \le c_j$），符号 $(-1)^{\sum t_j}$，然后从 $R$ 步中选 $t = \sum t_j$ 步放置这些非法向量（注意不同种非法向量值不同，所以放置时指定种类）。

---

第六步：具体公式

设非法向量种类集合 $D = \{d_1,\dots,d_m\}$，出现次数 $c_j$。

令：

$$\text{Ans} = \sum_{t_1=0}^{c_1} \cdots \sum_{t_m=0}^{c_m} (-1)^{t_1+\dots+t_m} \binom{c_1}{t_1} \cdots \binom{c_m}{t_m} \times [\text{剩余方案数}]. $$

其中 $\binom{c_j}{t_j}$ 表示从 $c_j$ 个相同的非法向量（编号不同但值相同）中选 $t_j$ 个强制使用（在容斥中表示“禁止”这些，但这里容斥是“禁用”，我们反过来做可能更顺）。

我换一种容斥方式：
令 $A_i$ 表示“使用了第 $i$ 个非法向量（按输入编号）”，则我们要求没有 $A_i$ 发生。

由容斥：

$$\text{合法方案} = \sum_{S \subseteq \{1,\dots,K\}} (-1)^{|S|} \times (\text{强制 $S$ 中非法向量至少各用一次，其它步任意的方案数}). $$

---

第七步：强制使用某些非法向量的计数

设 $S$ 中包含的不同非法向量值为 $\{d_1,\dots,d_t\}$，每个值 $d$ 在 $S$ 中出现 $s_d$ 次（$s_d \ge 1$）。

我们要从 $R$ 步中选 $|S|$ 步放置这些非法向量（注意相同值的非法向量不可区分，但这里 $S$ 中编号不同，所以必须区分？容斥时 $S$ 是编号集合，所以即使值相同，编号不同也算不同选择，因此排列时要乘上多重组合数）。

更简单做法：
令 $f(p_1,\dots,p_m)$ 表示强制第 $j$ 种非法向量恰好用 $p_j$ 次（$p_j \ge 0$）的方案数，总步数 $R$，总增量 $(T_x,T_y)$。

那么

$$f(p_1,\dots,p_m) = \binom{R}{p_1,\dots,p_m,R-\sum p_j} \times \text{剩余步的生成函数系数}. $$

其中剩余 $R-\sum p_j$ 步从 $F_0(x,y)$ 中选（可包含非法向量，因为已经固定了 $p_j$ 次）。

剩余步生成函数为 $F_0(x,y)^{R-\sum p_j}$，需要提取 $x^{T_x - \sum p_j d_j} y^{T_y - \sum p_j d_j}$ 的系数。注意 $dx=dy=d_j$ 对于非法向量，所以总 $x$ 和 $y$ 增量都减少 $\sum p_j d_j$。

---

第八步：提取 $F_0(x,y)^N$ 的系数

$F_0(x,y) = \frac{(1-x^{M_x+1})(1-y^{M_y+1})}{(1-x)(1-y)} - 1$。

写为：

$$F_0(x,y) = \sum_{a=0}^{M_x} \sum_{b=0}^{M_y} x^a y^b - 1. $$

所以 $F_0(x,y)^N$ 是多项式乘积。

但 $N = R-\sum p_j \le R \le 1000$，而 $T_x,T_y$ 很大，直接卷积不行，但可以用二维线性递推或二维前缀和优化，因为 $F_0(x,y)$ 的系数是简单的矩形区域全1。

一个技巧：$F_0(x,y) = (1 + x + \dots + x^{M_x})(1 + y + \dots + y^{M_y}) - 1$。

那么 $F_0(x,y)^N = \sum_{k=0}^N \binom{N}{k} (-1)^{N-k} (1+x+\dots+x^{M_x})^k (1+y+\dots+y^{M_y})^k$。

然后 $(1+x+\dots+x^{M_x})^k = \sum_{a=0}^{kM_x} \binom{k+a-1}{a} x^a$（允许 $a>kM_x$ 时系数为0，用组合数表示）。这里用组合数公式时要注意是否允许 $a>M_x$ 重复，实际上这里是可重复组合数，是对的。

所以我们可以分开 $x$ 和 $y$：

$$[x^{A} y^{B}] F_0(x,y)^N = \sum_{k=0}^N \binom{N}{k} (-1)^{N-k} \left( [x^A] (1+\dots+x^{M_x})^k \right) \left( [y^B] (1+\dots+y^{M_y})^k \right). $$

其中 $[x^A] (1+\dots+x^{M_x})^k = \sum_{t=0}^{\lfloor A/(M_x+1)\rfloor} (-1)^t \binom{k}{t} \binom{k+A-t(M_x+1)-1}{A-t(M_x+1)}$，这是用容斥去掉超过 $M_x$ 的限制的标准公式。

这样 $A = T_x - \sum p_j d_j$，$B = T_y - \sum p_j d_j$，$N = R-\sum p_j$。

---

第九步：算法步骤

1. 读入数据，对非法向量 $k_i$ 去重并统计每种出现次数 $c_j$。
2. 枚举每种非法向量的使用次数 $p_j$（$0 \le p_j \le c_j$，且 $p_j \le R$）。
3. 对每个 $(p_1,\dots,p_m)$，计算：
   • 总步数已用 $P = \sum p_j$，剩余步 $N = R-P$。
   • 总 $x,y$ 剩余增量 $A = T_x - \sum p_j d_j$，$B = T_y - \sum p_j d_j$。
   • 若 $A<0$ 或 $B<0$ 或 $N<0$，方案为0。
   • 计算 $W = [x^A y^B] F_0(x,y)^N$ 用上述公式。
   • 乘上多重组合数 $\binom{R}{p_1,\dots,p_m,N}$（注意非法向量种类不同，但同种内不可区分，所以是 $\frac{R!}{p_1!\dots p_m! N!}$）。
4. 根据容斥，符号为 $(-1)^{\sum p_j}$ 乘以 $\prod \binom{c_j}{p_j}$？这里要小心：
   我们容斥时是“禁用”某些非法向量，等价于“强制使用”某些非法向量，符号 $(-1)^{\sum t_j}$ 且选择方式 $\prod \binom{c_j}{t_j}$。
   所以总贡献为 $(-1)^{\sum p_j} \prod \binom{c_j}{p_j} \times \binom{R}{p_1,\dots,p_m,N} \times W$。
5. 对所有枚举求和，取模。

---

第十步：复杂度

$m \le 50$，但 $R \le 1000$，$p_j$ 枚举看起来很多，但总步数限制 $R$，所以总状态数约 $\binom{R+m}{m}$，当 $R=1000,m=50$ 时很大，不可行。

需要优化：注意到 $d_j$ 是 $G$ 倍数，$G$ 很大，所以非法向量值很大（$\ge 10000$），而 $T_x,T_y \le 10^6$，所以 $p_j$ 不能大（$\le 100$），因此枚举量其实不大。

实际可做。

---

总结

本题核心：

1. 用容斥处理非法对角线向量。
2. 将二维生成函数分解为两个一维问题。
3. 利用 $G$ 大导致非法向量稀疏，减少枚举量。
4. 用组合公式快速计算 $[x^A] (1+\dots+x^{M})^k$。