Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

jvjhfhg loves Magic Tower

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 69    Accepted Submission(s): 9

Problem 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$.**

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$

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


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2023 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2023-05-29 07:08:09, Gzip enabled