题目描述

Source: 51Nod #1838. Jabby 的网格

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$ 取模的值 。

1 2
1 2
2 1
1
1

2

数据范围与提示

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

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

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