Description

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

Input

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

Output

一个整数为方案数mod 10007（质数）后的值

Sample Input

Sample Output

Hint

数据规模

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

Source