题目描述
Source: 51Nod #1838. Jabby 的网格
Stange 来到了一个网格中,他想从 (0,0) 跳到 (Tx,Ty) 。
Stange 每一步只能向右上方跳,由于力气有限,每一步的横坐标变化不能超过 Mx ,纵坐标变化不能超过 My 。
即,如果他现在处于位置 (x,y) ,他下一步能跳到的 (newx,newy) 需要满足: x≤newx≤x+Mx,y≤newy≤y+My 。
同时,Stange 是个勤奋的人,他厌恶停在原地无所事事。因此每一步都不能够停在原地。
Stange 觉得这个游戏太没有挑战性了,于是他加入了一些限制:
有 K 个向量是非法的,这些向量形如 (ki,ki) ,会在读入中给出。也就是说,每一步 x,y 的增量不能同时等于 ki 。
幸运的是,所有的 ki 都是 G 的倍数。
现在 Stange 想求从 (0,0) ,跳恰好 R 步,跳到 (Tx,Ty) 的方案数。对 109+7 取
模。
输入格式
第一行两个正整数 Tx,Ty 。 (Tx,Ty≤106) 。
第二行两个正整数 Mx,My,(Mx,My≤106,Mx≤Tx,My≤Ty) 。
第三行两个正整数 R,G(R≤1000,10000≤G≤50000)(为方便理解题意,样例中不满足 10000≤G≤50000 的限制。大样例和评测的数据中都是满足的。)。
第四行一个非负整数 K(K≤50) 。
第五行(如果有的话),K 个正整数,表示 ki 。ki≤min(Mx,My),(保证 ki 是 G 的倍数,注意 ki 可能重复输入) 。
输出格式
一行一个非负整数,表示答案对 109+7 取模的值 。
样例
1 2
1 2
2 1
1
1
2
数据范围与提示
对于 30% 的数据, k=0,Tx,Ty≤1000 。
对于另外 30% 的数据, k=0 。
对于剩余 40% 的数据,无特殊性质。