题目描述

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 \leq 10^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 \le G \le 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\%$ 的数据，无特殊性质。