Problems
Present for Piglet
Present for Piglet
Once Piglet in a private conversation told Winnie the Pooh, that if there is a square \textbf{2}×\textbf{2}, and in his every cell is placed no more than an acorn, you can get a beautiful or ugly. Moreover, Piglet listed all the pretty pictures.
After some time, decided to make Winnie Piglet gift - a rectangle of height \textbf{m} and width \textbf{n} with acorns, in which all the squares of \textbf{2}×\textbf{2} - nice. Help Winnie the Pooh to count how many different ways to do this.
\InputFile
The first line of the input file contains the numbers \textbf{m} and \textbf{n}, (\textbf{2} ≤ \textbf{m} ≤ \textbf{8}, \textbf{2} ≤ \textbf{n} ≤ \textbf{100}). In the second row - integer, number of beautiful squares. Then there are the squares, a description of each - two lines, two of each: \textbf{1} is an acorn, \textbf{0} - none. All squares are different.
\OutputFile
Display the number of rectangles, in which all the squares - the good. Guaranteed that the answer does not exceed \textbf{10^9}.
Input example #1
8 8 2 0 1 1 0 1 0 0 1
Output example #1
2