Handshakes in Kindergarten

In A.D. 1770, Mr. Ji Yun traveled along the Jinxiang River and discussed the ways of friendship with the people. His words still influence the local community—even in kindergartens today. At the newly established Donoda Kindergarten, children and k teachers form an n × m rectangular grid. The teachers have mingled with the children, and while they sing together, the teachers give the children a task:

Each child (cells not occupied by teachers) must shake hands with exactly two of its adjacent (up, down, left, right) children. (Note that handshakes may only occur between children; a child cannot shake hands with a teacher, nor can a child shake hands with itself.)

Your task is to compute the number of different handshake arrangements that satisfy this condition. Since the answer can be very large, output the result modulo \(10^9+7\).

Note: Two handshake arrangements are considered different if there is at least one pair of children who shake hands in one arrangement and not in the other.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(k\) --- the number of rows, columns, and teachers respectively. Each of the following \(k\) lines contains two integers \(r\) and \(c\) (1-indexed), denoting the position of a teacher in the grid. All cells that are not occupied by a teacher contain a child.

outputFormat

Output a single integer: the number of handshake arrangements modulo \(10^9+7\), where every child shakes hands with exactly two adjacent children.

sample

2 2 0

1