Uncle Jacques has purchased some colorful floor panels for the dance floor of his club. Every Friday his employees will rearrange the panels so that the disco dance floor will have a new and exciting look. He has purchased a large supply of panels with seven different shapes. Each panel consists of four 1 foot squares as depicted below:
_
_ _ _ _ _ | |
| | | | _| | | |_ | |_ _ _ | |
| |_ _| | | _| |_ | | _| | | | |
|_ _| |_ _| |_| |_| |_| |_ _| |_|
1 2 3 4 5 6 7
Uncle Jacques needs to know if his dance floor can be completely covered using these panels. He also needs to know how many different patterns his employees can create on the dance floor. The panels can be rotated in 90-degree increments, they cannot overlap, they cannot extend past the edge of the dance floor, and they must cover the dance floor completely.
Your first job is to determine whether the dance floor can be completely covered. Your second job is to determine the number of different patterns that can be created by rearranging the panels. Patterns are considered distinct if the borders between panels are different. For example, for a 4 foot by 2 foot dance floor, there are 4 distinct patterns:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |_ _ | | _ _| | |_ _ _ _| | | | |_ _ _|_| |_|_ _ _| |_ _ _ _| |_ _|_ _|
Rotations of patterns are also considered distinct. For example, the following four patterns are distinct:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _|_ | | _ _| | |_ _ _ _| | |_ _ | | | | | |_| | | | | | | | | |_| |_|_ _|_| | |_ _| | | |_ _| | | |_ _| | |_ _ _ _| |_ _ _|_| |_ _|_ _| |_|_ _ _|
Your program must accept the length and width of the dance floor in feet. There can be any number of dance floor measurements in the input. The dance floor will not be larger than 36 square feet.
There will only be one line of output for each set or measurements. Your program must return the number of distinct patterns, which completely cover the dance floor. If the floor cannot be completely covered, your program must return zero.
2 4 3 3 3 4 4 4
4 0 23 117