404188: GYM101446 B Tiling
Description
You have a 7 × n rectangular grid that you want to cover with L-triominoes and 1 × 1 squares. You have exactly k L-triominoes and 7n - 3k squares. An L-triomino can be rotated arbitrarily. Naturally, each cell of the grid should be covered by exactly one piece. Additionally, some of the cells can not be covered by a 1 × 1 square.
Count the number of possible tilings modulo 109 + 33.
InputThe first line contains two integers n and k (2 ≤ n ≤ 100, 7n - 20 ≤ 3k ≤ 7n).
The second line contains an integer m (0 ≤ m ≤ 7n): the number of cells that are forbidden to cover with a 1 × 1 square.
Each of the next m lines contains two integers xi and yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ 7): column and row index of the respective forbidden cell.
OutputPrint the answer modulo 109 + 33.
ExampleInput2 3Output
9
1 1
1 2
1 3
1 5
2 1
2 2
2 3
2 4
2 5
2