[SDWC2018]网格

内存限制：128 MB 时间限制：1000 ms

Stange 来到了一个网格中，他想从 $(0,0)$ 跳到 $(T_x,T_y)$。

Stange 每一步只能向右上方跳，由于力气有限，每一步的横坐标变化不能超过 $M_x$，纵坐标变化不能超过 $M_y$。

即，如果他现在处于位置 $(x,y)$，他下一步能跳到的$(\text{newx},\text{newy})$ 需要满足：$x\leq \text{newx}\leq x+M_x , y\leq \text{newy}\leq y+M_y$。

同时，Stange 是个勤奋的人，他厌恶停在原地无所事事。因此每一步都不能够停在原地。

Stange 觉得这个游戏太没有挑战性了，于是他加入了一些限制：

有 $K$ 个向量是非法的，这些向量形如 $(k_i,k_i)$，会在读入中给出。也就是说，每一步 $x,y$ 的增量不能同时等于 $k_i$。

幸运的是，所有的 $k_i$ 都是 $G$ 的倍数。

现在 Stange 想求从 $(0,0)$，跳恰好 $R$ 步，跳到 $(T_x,T_y)$ 的方案数。对 $10^9+7$ 取模。

第一行两个正整数 $T_x,T_y$。$(T_x,T_y\leq10^6)$。

第二行两个正整数 $M_x,M_y, (M_x,M_y \leq 10^6,M_x \leq T_x , M_y \leq T_y)$。

第三行两个正整数 $R,G (R \leq 1000 , 10000 \leq G \leq 50000)$（为方便理解题意，样例中不满足 $10000 \leq G \leq 50000$ 的限制。大样例和评测的数据中都是满足的）。

第四行一个非负整数 $K (K \leq 50)$。

第五行（如果有的话），$K$ 个正整数，表示 $k_i$。$k_i \leq \min(M_x,M_y)$，（保证 $k_i$ 是 $G$ 的倍数，注意 $k_i$ 可能重复输入）。

一行一个非负整数，表示答案对 $10^9+7$ 取模的值。

对于 $30\%$的数据，$k=0, T_x,T_y \leq 1000$。

对于另外 $30\%$ 的数据，$k=0$。

对于剩余 $40\%$ 的数据，无特殊性质。

C0727 [SDWC2018]网格