Present for Piglet#1860
Once Piglet, in a private conversation, told Winnie the Pooh that if there is a square 2\times 2, and in each cell there is at most one acorn, the picture can be either beautiful or not. Moreover, Piglet listed all the beautiful pictures.
After some time, Winnie decided to make Piglet a gift — a rectangle with height and width , filled with acorns, such that every 2\times 2 square within it is beautiful. Help Winnie the Pooh count how many different ways he can do this.
The first line contains natural numbers and (2 \leq m \leq 8; 2 \leq n \leq 100). The second line contains a natural number, the number of beautiful squares. Then, descriptions of the squares follow: for each, two lines with two numbers each. indicates an acorn, indicates none. All squares are different.
Output the number of rectangles in which all 2\times 2 squares are beautiful. It is guaranteed that the answer does not exceed 10^9.
Beispiel 1