<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

131. Hardwood floor

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


The banquet hall of Computer Scientists' Palace has a rectangular form of the size M x N (1<=M<=9, 1<=N<=9). It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:
1) rectangles (2x1)
2) corners (squares 2x2 without one 1x1 square)
You have to determine X - the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.


Input

The first line contains natural number M. The second line contains a natural number N.


Output

First line should contain the number X, or 0 if there are no solutions.


Sample Input

2 3
Sample Output

5
Author	: Herman "Smash" Narkaytis, Paul "Stingray" Komkoff
Resource	: 5th Southern Subregional Contest. Saratov 2002
Date	: 2002-10-10

<|response|>
1. Abridged problem statement  
Given an M×N grid (1≤M,N≤9), count the number of ways to tile it exactly with  
• 2×1 dominoes (can be placed horizontally or vertically), and  
• L-shaped trominoes formed by a 2×2 block missing one cell (all four rotations).  
Output the total number of tilings (0 if none).

2. Key observations  
• If one dimension is 1, only dominoes can fit. A 1×L board can be tiled by dominoes iff L is even, yielding exactly 1 way; otherwise 0.  
• We can assume the smaller dimension is the width W (swap M,N if needed) so W≤9.  
• We scan the grid in row-major order, cell by cell, maintaining a bitmask state of size W+1:  
  – Bits 0..W−1 mark which cells in the current row (from the current column onward, with wrap as we shift) are already covered.  
  – Bit W marks whether the cell above the current position is covered by a piece extending downward.  
• Define dp[p][mask] = number of ways after processing the first p cells (in row-major order) with the current mask. The final answer is dp[M·N][full_mask], where full_mask = (1<<(W+1))−1.

3. Full solution approach  
1) Handle the trivial 1×L case: if M==1 or N==1, let L=max(M,N); answer = 1 if L is even, else 0.  
2) Ensure W = min(M,N) and H = max(M,N). Total cells T = W×H.  
3) Let B = W+1, full_mask = (1<<B)−1. Initialize dp[0][0] = 1, all other dp[0][*] = 0.  
4) For p from 0 to T−1 do:  
   a) Compute r = p / W, c = p % W.  
   b) For each mask from 0 to full_mask with dp[p][mask]>0, let ways = dp[p][mask].  
      i) Check if current cell (r,c) is already covered:  
         covered_from_left_or_row = (mask & 1) != 0  
         covered_from_above        = (mask & (1<<W)) != 0  
         If either is true, simply shift the mask: new_mask = (mask<<1) & full_mask, then dp[p+1][new_mask] += ways.  
      ii) Otherwise the cell is free. Try every piece placement that covers (r,c), verifying boundaries and that all involved bits are unset, then build the new mask by setting the bits for newly covered cells (including marking bit W if you cover the cell below), shift left by 1, and add ways.  
         • Horizontal domino covering (r,c),(r,c+1) if c+1<W and bit 1 of mask==0.  
         • Vertical   domino covering (r,c),(r+1,c) if r+1<H.  
         • L-tromino in its four rotations:  
           1) cells {(r,c),(r,c+1),(r+1,c)}  
           2) cells {(r,c),(r+1,c),(r+1,c+1)}  
           3) cells {(r,c),(r,c+1),(r+1,c+1)}  
           4) cells {(r,c),(r+1,c),(r+1,c−1)}  
5) The answer is dp[T][full_mask].

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, N;
    cin >> M >> N;

    // Handle the 1×L trivial case
    if (M == 1 || N == 1) {
        int L = max(M, N);
        // Only dominoes fit; exactly one tiling if L is even
        cout << ((L % 2 == 0) ? 1 : 0) << "\n";
        return 0;
    }

    // Let W = smaller dimension (width), H = larger (height)
    int W = min(M, N), H = max(M, N);
    int T = W * H;

    // We'll keep a bitmask of length B = W+1
    // bits [0..W-1]: occupancy in the current row from current col onward
    // bit W       : occupancy from a piece reaching down from the row above
    int B = W + 1;
    int full_mask = (1 << B) - 1;

    // dp[p][mask]: number of ways after filling p cells, with profile=mask
    vector< vector<int64> > dp(T+1, vector<int64>(1 << B, 0));
    dp[0][0] = 1;

    // Iterate over each cell in row-major order
    for (int p = 0; p < T; p++) {
        int r = p / W, c = p % W;
        for (int mask = 0; mask <= full_mask; mask++) {
            int64 ways = dp[p][mask];
            if (ways == 0) continue;

            // Check if current cell is already covered
            bool from_row   = (mask & 1) != 0;         // bit 0
            bool from_above = (mask & (1 << W)) != 0;  // bit W
            if (from_row || from_above) {
                // Just shift the mask to move to next cell
                int nm = (mask << 1) & full_mask;
                dp[p+1][nm] += ways;
                continue;
            }

            // The cell (r,c) is free, try placing each piece

            // 1) Horizontal domino (r,c),(r,c+1)
            if (c+1 < W && ((mask & 2) == 0)) {
                // set bits 0 and 1, then shift
                int nm = ((mask | 3) << 1) & full_mask;
                dp[p+1][nm] += ways;
            }

            // 2) Vertical domino (r,c),(r+1,c)
            if (r+1 < H) {
                // mark bit W for the cell below
                int nm = ((mask | (1 << W)) << 1) & full_mask;
                dp[p+1][nm] += ways;
            }

            // 3) L-tromino shape {(r,c),(r,c+1),(r+1,c)}
            if (c+1 < W && r+1 < H && ((mask & 2) == 0)) {
                int t = mask | 3        // cover (r,c),(r,c+1)
                        | (1 << W);     // cover (r+1,c)
                int nm = (t << 1) & full_mask;
                dp[p+1][nm] += ways;
            }

            // 4) L-tromino shape {(r,c),(r+1,c),(r+1,c+1)}
            if (c+1 < W && r+1 < H && ((mask & (1 << W)) == 0)) {
                // mark bit W for (r+1,c) and bit (W-1) for (r+1,c+1) in the row mask
                int t = mask | (1 << W) | (1 << (W-1));
                int nm = (t << 1) & full_mask;
                dp[p+1][nm] += ways;
            }

            // 5) L-tromino shape {(r,c),(r,c+1),(r+1,c+1)}
            if (c+1 < W && r+1 < H
                && ((mask & 2) == 0)
                && ((mask & (1 << W)) == 0)) {
                int t = mask | 2            // cover (r,c+1)
                        | (1 << W)         // cover (r+1,c)
                        | (1 << (W-1));    // cover (r+1,c+1)
                int nm = (t << 1) & full_mask;
                dp[p+1][nm] += ways;
            }

            // 6) L-tromino shape {(r,c),(r+1,c),(r+1,c-1)}
            if (r+1 < H && c-1 >= 0
                && ((mask & (1 << W)) == 0)
                && ((mask & (1 << (W-1))) == 0)) {
                // mark bit W for (r+1,c) and bit (W-1) for (r+1,c-1)
                int t = mask | (1 << W) | (1 << (W-1));
                int nm = (t << 1) & full_mask;
                dp[p+1][nm] += ways;
            }
        }
    }

    // The only valid final profile is full_mask
    cout << dp[T][full_mask] << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
def count_tilings(M, N):
    # Handle 1×L case: only dominoes fit
    if M == 1 or N == 1:
        L = max(M, N)
        return 1 if (L % 2 == 0) else 0

    # Let W = smaller dimension (width), H = larger (height)
    W, H = sorted([M, N])
    T = W * H
    B = W + 1
    full_mask = (1 << B) - 1

    # dp[p][mask]: ways after filling p cells, with profile=mask
    dp = [ [0]*(1<<B) for _ in range(T+1) ]
    dp[0][0] = 1

    for p in range(T):
        r, c = divmod(p, W)
        for mask in range(1<<B):
            ways = dp[p][mask]
            if ways == 0:
                continue

            # Is current cell covered?
            from_row   = (mask & 1) != 0       # bit 0
            from_above = (mask & (1<<W)) != 0  # bit W
            if from_row or from_above:
                # shift mask and move on
                nm = (mask << 1) & full_mask
                dp[p+1][nm] += ways
                continue

            # cell (r,c) is free: try each tile

            # 1) Horizontal domino
            if c+1 < W and not (mask & 2):
                nm = ((mask | 3) << 1) & full_mask
                dp[p+1][nm] += ways

            # 2) Vertical domino
            if r+1 < H:
                nm = ((mask | (1<<W)) << 1) & full_mask
                dp[p+1][nm] += ways

            # 3) L-shape {(r,c),(r,c+1),(r+1,c)}
            if c+1 < W and r+1 < H and not (mask & 2):
                t = mask | 3 | (1<<W)
                nm = (t << 1) & full_mask
                dp[p+1][nm] += ways

            # 4) L-shape {(r,c),(r+1,c),(r+1,c+1)}
            if c+1 < W and r+1 < H and not (mask & (1<<W)):
                t = mask | (1<<W) | (1<<(W-1))
                nm = (t << 1) & full_mask
                dp[p+1][nm] += ways

            # 5) L-shape {(r,c),(r,c+1),(r+1,c+1)}
            if c+1 < W and r+1 < H and not (mask & 2) and not (mask & (1<<W)):
                t = mask | 2 | (1<<W) | (1<<(W-1))
                nm = (t << 1) & full_mask
                dp[p+1][nm] += ways

            # 6) L-shape {(r,c),(r+1,c),(r+1,c-1)}
            if r+1 < H and c-1 >= 0 and not (mask & (1<<W)) and not (mask & (1<<(W-1))):
                t = mask | (1<<W) | (1<<(W-1))
                nm = (t << 1) & full_mask
                dp[p+1][nm] += ways

    return dp[T][full_mask]

if __name__ == "__main__":
    M, N = map(int, sys.stdin.read().split())
    print(count_tilings(M, N))
```