#3096. 跳棋

内存限制:128 MiB 时间限制:5 Sec

题目描述

一个无限大的边长为1的网格地图上一开始有一个跳棋在(0,0),要跳到(Tx,Ty)。每次在x方向的位移量为[0,Mx], 每次在y方向的位移量为[0,My],每次必须移动,不能留在原位置上。现在想知道通过R次跳到目标的方案数。限制条件是:给定n个数字bi,要求每次跳的向量不能为(bi,bi)。

输入格式

第一行六个整数Tx,Ty,Mx,My,R,n
第二行n个整数为bi

输出格式

一个整数为方案数mod 10007(质数)后的值

样例

样例输入


			
2 2 1 1 2 0

样例输出


			
1


数据范围与提示

数据规模

100%的数据保证1<=Tx,Ty,Mx,My<=800,1<=R<=1600,0<=n<=50,输入数据保证每个bi都是10的倍数,1<=bi<=min(Mx,My),且bi各不相同。