#6374. 「SDWC2018 Day1」网格

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: FancyDreams

题目描述

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\% 的数据,无特殊性质。