本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1144. Dominoes


Description

Orz likes to play dominoes. Now giving an n*m chessboard and k dominoes whose size are 1*2, Orz finds that there is exactly one grid empty, so that he can move dominoes without overlapping them. An initial situation is given, he wants to know how many final situation could be achieved, except the initial situation. Note every domino is different, as they have their own serial number. Since the answer may be very large, please output the answer modulo 1000000009. 

Input

There will be multiple test cases. For each test case:
The first line contains three integers: n, m, k(n ≤ 9, m ≤ 10000).
The following k lines, each line contains four integers: a  b  c  d, indicating that this domino occupies (a, b) and (c, d). 
The input guarantees that the domino does not overlap, and there is exactly one empty grid.

Output

For each test cases, output the answer modulo 1000000009.

Samples

Input Copy
5 5 12
1 1 2 1 
1 2 2 2 
1 3 2 3 
1 4 1 5
2 4 2 5
3 4 3 5
3 1 3 2
4 1 4 2
5 1 5 2
4 3 5 3
4 4 5 4
4 5 5 5
Output
8

Source

第九届山东省赛
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1017. 2018 SD ACM
My history solutions

You didn't submit any solution!
Submit your solution

Login Register