跳棋

时间限制:5s      空间限制:128MB

题目描述

一个无限大的边长为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各不相同。


题目来源

没有写明来源