You all must be familiar with the chess-board having $8*8$ squares of alternate black and white cells. Well, here we have for you a similar $N*M$ size board with similar arrangement of black and white cells.

A few of these cells have Horses placed over them. Each horse is unique. Now these horses are not the usual horses which could jump to any of the 8 positions they usually jump in. They can move only if there is another horse on one of the 8-positions that it can go to usually and then both the horses will swap their positions. This swapping can happen infinitely times.

A photographer was assigned to take a picture of all the different ways that the horses occupy the board! Given the state of the board, calculate answer. Since this answer may be quite large, calculate in modulo $10$⁹7.

Input:

First line contains T which is the number of test cases.

T test cases follow first line of each containing three integers N, M and Q where $N,M$ is the size of the board and Q is the number of horses on it.

Q lines follow each containing the 2 integers X and Y which are the coordinates of the Horses.

Output:

For each test case, output the number of photographs taken by photographer.

Constraints:

• 1 ≤ T ≤ $10$
• 1 ≤ $N,M$ ≤ $10$³
• 1 ≤ Q ≤ $N*M$

Scoring:

• 1 ≤ T ≤ $10, 1$ ≤ $N,M$ ≤ $10$: (20 pts)
• 1 ≤ T ≤ $10, 1$ ≤ $N,M$ ≤ $100$: (30 pts)
• Original Constraints : (50 pts)