Bee Seungyeon

Seungyeon, who lives in another world, is a bee.

The hive Seungyeon lives in has a somewhat unusual structure. The hive is an (N) by (M) grid, and each cell is a regular hexagon. When two cells in the same row are compared, the cell in an even-numbered column sits half a cell lower than the cell in an odd-numbered column. The figure below shows an example of a hive made of a 3 by 4 grid.

Two hexagonal cells are adjacent if they share an edge. Each edge of a hexagonal cell has a door through which Seungyeon can move to the adjacent cell, but to keep traffic in the hive orderly, a cell only allows movement to the cell below, the cell above-right, and the cell below-right. The hive may also contain hole cells, and Seungyeon cannot move into a hole cell.

To avoid a mutant virus spreading rapidly among the bees, Seungyeon has been staying inside the hive. Bored out of her mind, Seungyeon wants to know the number of paths from the cell in row (1), column (1) to the cell in row (N), column (M) that never leave the hive.

Count the number of paths so that Seungyeon, stuck in self-quarantine, is no longer frustrated!

The first line gives (N) and (M), separated by a space.

The next line gives (K), the number of hole cells.

The following (K) lines give the hole cell information (x_i), (y_i), separated by a space. This means the (i)-th hole cell is in row (x_i), column (y_i). All hole cells are in distinct positions.

The cell in row (1), column (1) and the cell in row (N), column (M) are guaranteed not to be holes.

Print the number of paths from the cell in row (1), column (1) to the cell in row (N), column (M) of the hive, modulo (10^9+7).

• 2 ≤ (N) ≤ 1,000
• 2 ≤ (M) ≤ 1,000
• 0 ≤ (K) ≤ min((NM) - 2, 104)
• 1 ≤ (x_i) ≤ (N)
• 1 ≤ (y_i) ≤ (M)