P6128 [JSOI2012] Kindergarten Game

In the year $1770$, Mr. Ji Yun passed by Jingxiang River and talked with local people about life and kindness. The way of making friends that he told people has been passed down to this day, deeply influencing the locals, even the children in a kindergarten. One day, the children and teachers of Duonuoda New Kindergarten sat in rows, forming an $n \times m$ rectangular grid. There are $k$ teachers, and they are mixed into this grid, happily singing with the children: “Hand in hand, we will always be good friends!”. So the teachers要求 each child to hold hands with any two of the children around them (i.e., in the four directions: up, down, left, right). As the smartest child in the kindergarten, you immediately realized that this is not just a simple game, but a very meaningful problem. You want to know how many different hand-holding plans there are such that every child can hold hands with exactly two adjacent children. Of course, each child can only hold hands with other children, not with teachers. No child is allowed to hold hands with themselves (i.e., holding their own left hand with their right hand). You only need to know the number of plans. Since the answer may be too large, output it modulo $1000000007$.

The first line contains three integers $n$, $m$, and $k$, as described above. The next $k$ lines each contain two integers $x$ and $y$, describing the position of a teacher.

Output one integer, the result of the answer modulo $10^9+7$.

For $100\%$ of the testdata, $1 \le n \le 8$, $1 \le m \le 2^{31}-1$, $1 \le k \le 100$. Translated by ChatGPT 5