题目描述

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

输入格式

第一行六个整数 $tx,ty,mx,my,r,n$。

第二行 $n$ 个整数为 $b_i$。

输出格式

一个整数为方案数 $\bmod 10007$（质数）后的值。

2 2 1 1 2 0

1

数据规模与约定

对于 $100\%$ 的数据，$1\le tx,ty,mx,my\le 800$，$1\le r\le 1600$，$0\le n\le 50$，输入数据保证每个 $b_i$ 都是 $10$ 的倍数，$1\le bi\le \min(mx,my)$，且 $b_i$ 各不相同。