<|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++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;

void read() { cin >> n >> m; }

void solve() {
    // This is a standard problem for DP with a broken profile, although we need
    // to consider some cases.

    // vector<vector<int64_t>> can_cover(1 << m, vector<int64_t>(1 << m,
    // false));

    // can_cover[0][0] = 1;
    // for(int mask = 0; mask < (1 << m); mask++) {
    //     for(int nmask = 0; nmask < (1 << m); nmask++) {
    //         int i = m - 1;
    //         while(i >= 0 && !(mask & (1 << i)) && !(nmask & (1 << i))) {
    //             i--;
    //         }

    //         if(i == -1) {
    //             continue;
    //         }

    //         if((mask & (1 << i)) && (nmask & (1 << i))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << i)][nmask ^ (1 << i)];
    //         }

    //         if(i > 0 && (mask & (1 << i)) && (mask & (1 << (i - 1)))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << i) ^ (1 << (i - 1))][nmask];
    //         }

    //         if(i > 0 && (nmask & (1 << i)) && (nmask & (1 << (i - 1)))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask][nmask ^ (1 << i) ^ (1 << (i - 1))];
    //         }

    //         if(i > 0 && (mask & (1 << i)) && (nmask & (1 << (i - 1))) &&
    //            (nmask & (1 << i))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << i)]
    //                          [nmask ^ (1 << i) ^ (1 << (i - 1))];
    //         }

    //         if(i > 0 && (mask & (1 << (i - 1))) && (nmask & (1 << i)) &&
    //            (nmask & (1 << (i - 1)))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << (i - 1))]
    //                          [nmask ^ (1 << i) ^ (1 << (i - 1))];
    //         }

    //         if(i > 0 && (nmask & (1 << i)) && (mask & (1 << (i - 1))) &&
    //            (nmask & (1 << i))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << (i - 1))]
    //                          [nmask ^ (1 << i) ^ (1 << (i - 1))];
    //         }

    //         if(i > 0 && (nmask & (1 << i)) && (mask & (1 << (i - 1))) &&
    //            (mask & (1 << (i - 1)))) {
    //             can_cover[mask][nmask] +=
    //                 can_cover[mask ^ (1 << (i - 1))]
    //                          [nmask ^ (1 << i) ^ (1 << (i - 1))];
    //         }

    //         cout << bitset<3>(mask) << '\n'
    //              << bitset<3>(nmask) << '\n'
    //              << can_cover[mask][nmask] << '\n';
    //         cout << ">>>> " << i << '\n';
    //         cout << '\n';
    //     }
    // }

    // vector<vector<int64_t>> dp(n + 1, vector<int64_t>(1 << m, 0));
    // dp[0][(1 << m) - 1] = 1;
    // for(int i = 1; i <= n; i++) {
    //     for(int mask = 0; mask < (1 << m); mask++) {
    //         for(int nmask = 0; nmask < (1 << m); nmask++) {
    //             dp[i][nmask] +=
    //                 can_cover[mask ^ ((1 << m) - 1)][nmask] * dp[i -
    //                 1][mask];
    //         }
    //     }
    // }

    if(n == 1 || m == 1) {
        cout << (n + m) % 2 << endl;
        return;
    }

    vector<vector<int64_t>> dp(n * m + 1, vector<int64_t>(1 << (m + 1), 0));
    int total_mask = (1 << (m + 1)) - 1;

    dp[0][0] = 1;
    for(int p = 0; p < n * m; p++) {
        for(int mask = 0; mask < (1 << (m + 1)); mask++) {
            if(!dp[p][mask]) {
                continue;
            }

            int i = p / m, j = p % m;
            if((p > m && (mask & (1 << m))) || p <= m) {
                dp[p + 1][(mask << 1) & total_mask] += dp[p][mask];
            }

            //  XXXXXX
            // X..
            if(j > 0 && !(mask & 1)) {
                if((p > m && (mask & (1 << m))) || p <= m) {
                    dp[p + 1][((mask << 1) | 3) & total_mask] += dp[p][mask];
                }
            }

            //  X.XXXX
            // XX.
            if(i > 0 && !(mask & (1 << (m - 1)))) {
                if((p > m && (mask & (1 << m))) || p <= m) {
                    dp[p + 1][((mask << 1) | 1 | (1 << m)) & total_mask] +=
                        dp[p][mask];
                }
            }

            //  X.XXXX
            // X..
            if(i > 0 && j > 0 && !(mask & (1 << (m - 1))) && !(mask & 1)) {
                if((p > m && (mask & (1 << m))) || p <= m) {
                    dp[p + 1][((mask << 1) | 3 | (1 << m)) & total_mask] +=
                        dp[p][mask];
                }
            }

            //  ..XXXX
            // XX.
            if(i > 0 && j > 0 && !(mask & (1 << (m - 1))) &&
               !(mask & (1 << m))) {
                dp[p + 1][((mask << 1) | 1 | (1 << m)) & total_mask] +=
                    dp[p][mask];
            }

            //  .XXXXX
            // X..
            if(i > 0 && j > 0 && !(mask & (1 << m)) && !(mask & 1)) {
                dp[p + 1][((mask << 1) | 3) & total_mask] += dp[p][mask];
            }

            //  X..XXX
            // XX.
            if(i > 0 && j + 1 < m && !(mask & (1 << (m - 1))) &&
               !(mask & (1 << (m - 2)))) {
                if((p > m && (mask & (1 << m))) || p <= m) {
                    dp[p + 1]
                      [((mask << 1) | 1 | (1 << (m - 1)) | (1 << m)) &
                       total_mask] += dp[p][mask];
                }
            }
        }
    }

    cout << dp[n * m][total_mask] << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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))
```