Interesting Round‐Trip Route

In a new city, modeled as an (n \times m) rectangular grid, some cells contain tourist attractions. A group of students starts at cell ((1,1)) and wants to travel to cell ((n,m)) and then return to the start. They must visit every attraction. They move to an adjacent cell (i.e. if (|a-c|+|b-d|=1)) in one minute. Note that the minimal time to go from ((1,1)) to ((n,m)) is (n+m-2) minutes, so the round–trip takes exactly (2n+2m-4) minutes if both halves are shortest paths. Furthermore, the route is required to be simple: each cell may be visited at most once (except that ((1,1)) is the start and end) and the route must pass through every cell that contains an attraction. We call a route that meets these conditions an interesting route.

Your task is to count, modulo (10^9+7), the number of different interesting routes.

Explanation: A shortest path from ((1,1)) to ((n,m)) must consist of exactly (n-1) moves down and (m-1) moves right. Hence a round–trip (going and returning) has exactly (2n+2m-4) moves. However, the condition that each cell is visited at most once (except the starting cell) forces the two halves of the journey to have no common cells except ((1,1)) and ((n,m)). In other words, if we denote the forward path by (P) and the return path by (Q) (when reversed, it becomes a right/down path from ((1,1)) to ((n,m))), then (P) and (Q) must be vertex–disjoint (except at the endpoints). Only those pairs ((P,Q)) whose union contains all attractions are considered valid.

It can be shown that under these constraints the answer is always finite. (Note that (n) and (m) are constrained so that a direct dynamic programming solution is feasible.)

inputFormat

The first line contains three integers: \(n\), \(m\) and \(k\) \( (2 \le n, m \le 10,\ 0 \le k \le 10)\) --- the number of rows, the number of columns, and the number of attractions, respectively.

Then \(k\) lines follow, each containing two integers \(x_i\) and \(y_i\) \( (1 \le x_i \le n,\ 1 \le y_i \le m)\), indicating that cell \((x_i,y_i)\) contains an attraction. (Attractions may appear on any cell, including \((1,1)\) and \((n,m)\)).

outputFormat

Output a single integer: the number of interesting routes modulo \(10^9+7\).

sample

2 2 0

2