Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
The city is building a centralized heating system in some of the city districts. City district occupies rectangular area and consists of square blocks arranged in a grid. Centralized heating system is a closed circuit of pipes that will be used to run hot water through every block in the district. The city council is considering different layouts of pipes for each district. In order to minimize the total length of pipes but still provide hot water to every block in the district, exactly one pipe must run through every block. A pipe in every block must be connected to the pipes in two neighboring blocks. So, there are at most six possible pipe configurations in every block:
In order to plan their planning activities, the city council wants to know the number of different possible pipe layouts for a given city district. For example, there are exactly 6 different pipe layouts for a district with 16 blocks arranged into 4 by 4 grid:
The input file contains two integer numbers r (r > 1) and c (c > 1). They specify, correspondingly, the number of rows and columns of blocks in the district. The total number of blocks in a district does not exceed 100 (r × c ≤ 100).
Output the number of different possible pipe layouts for this district.
Andrew Stankevich Contest 16