Tiling the Computer Lab

The computer lab can be seen as an \( n \times m \) rectangle. In order to ensure the Blue Bridge competition goes smoothly, the organizers have decided to re-tile the computer lab. They have two special types of tiles (see Figure 1) available. The shapes are as follows (rotations allowed):

• Tile Type 1 (Domino): Covers 2 adjacent cells. It can be placed horizontally (covering \( (0,0) \) and \( (0,1) \)) or vertically (covering \( (0,0) \) and \( (1,0) \)).
• Tile Type 2 (L-shaped Tromino): Covers 3 cells forming an L shape (a 2\( \times \)2 square with one cell missing). In its 4 possible rotations the relative coordinates (with the top‐left cell as the anchor) are:
  \( L_1 = \{(0,0), (1,0), (0,1)\} \),
  \( L_2 = \{(0,0), (0,1), (1,1)\} \),
  \( L_3 = \{(0,1), (1,0), (1,1)\} \),
  \( L_4 = \{(0,0), (1,0), (1,1)\} \).

Your task is to compute the number of ways to completely tile the \( n \times m \) lab using any number of these two types of tiles. Tiles cannot overlap and must exactly cover the board. Note that the board may not be tileable for some \( n \) and \( m \) (in which case, the answer is 0). You can assume that \( n \) and \( m \) are small enough (e.g. \( n, m \leq 4 \)) so that a complete search is feasible.

Input Format: Two integers \( n \) and \( m \) separated by a space.

Output Format: Output a single integer representing the number of tiling schemes.

inputFormat

The input consists of a single line with two space‐separated integers \( n \) and \( m \), representing the dimensions of the computer lab.

outputFormat

Output a single integer: the number of ways to tile the \( n \times m \) board using the two types of tiles.

sample

2 2

2