jvjhfhg loves Magic Tower

Time Limit: 5000/2500 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

Jvjhfhg is a pupil who loves a flash game called "Magic Tower". He always searches for various "Magic Towers".

Jvjhfhg finds a game called "Magic Tower - Step the Lamps".

In an $n \times m$ map($m$ is an odd number) where the first coordinate on the first line is $(1, 1)$ and the last coordinate on the last line is $(n, m)$, there's a "lamp" on every checker, which has two mode: on and off. At first, all "lamps" are switched OFF. Jvjhfhg sets off from a special checker $(0, \frac{(m + 1)}{2})$ which as well as $(n + 1, \frac{(m + 1)}{2})$ has no "lamp". Of course stepping on these two checkers is available. When Jvjhfhg goes onto a has-lamp checker whose coordinate is $(x, y)$, the mode of the light of the checker, as well as those of the lights of $k + 1$ checker, namely $(x + x_1, y + y_1),(x + x_2, y + y_2),\cdots ,(x + x_k, y + y_k)$, will alter. When all the "lamps" are on, the game ends. The author found that the game is so effortless when many checkers can only alter its own if the sum of ${x}_{i}$ and ${y}_{i}$ is too large or the map is too small, so he sets: $|xi| + |yi| \leq 5$ and $n,m \geq 5$.

Jvjhfhg completes the game soonly, but he's still wondering how many paths can end the game. He finds that there could be infinite possibilities, so he decides that if all with-lamp checkers are passed for the number of times of same parities in two paths, these two paths are counted as one.

**Print the answer modulo ${10}^{9}+7$.**

Input

The first line contains an integer $T$ denoting the number of cases.

For each case, the first line contains three integers $n,m,k$,while $m$ is odd.

The next $k$ lines each contains two integers $x_i,y_i$. Data ensures that $|xi| + |yi| \leq 5$.

$1 \leq T \leq 5$, $5 \leq n, m \leq 100$, $1 \leq k \leq 10$

Output

For each case, print a single line with an integer denoting the answer.

Sample Input

1 5 5 4 -1 0 1 0 0 1 0 -1

Sample Output

4

Hint

wange2014

Source

BestCoder Round #90

提交代码