Present for Piglet
Once Piglet in a private conversation told Winnie the Pooh, that if there is a square 2×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 m and width n with acorns, in which all the squares of 2×2 - nice. Help Winnie the Pooh to count how many different ways to do this.
Input
The first line of the input file contains the numbers m and n, (2 ≤ m ≤ 8, 2 ≤ n ≤ 100). In the second row - integer, number of beautiful squares. Then there are the squares, a description of each - two lines, two of each: 1 is an acorn, 0 - none. All squares are different.
Output
Display the number of rectangles, in which all the squares - the good. Guaranteed that the answer does not exceed 10^9.