#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

int H, W;

bool inside(int i, int j){
     return 0 <= i && i < H && 0 <= j && j < W;
}

bool exist(vector<vector<int>>& field, int i, int j){
    return !inside(i, j) || field[i][j] != 0;
}

bool different(vector<vector<int>>& field, int ai, int aj, int bi, int bj){
    return inside(ai, aj) && inside(bi, bj) && field[ai][aj] != 0 && field[bi][bj] != 0 && field[ai][aj] != field[bi][bj];
}

bool able(vector<vector<int>>& field, int i, int j){
    return !(different(field, i-1, j-1, i-1, j) && different(field, i, j-1, i-1, j-1)) && !(different(field, i+1, j-1, i+1, j) && different(field, i+1, j-1, i, j-1));
}

int dfs(vector<vector<int>>& field, int idx){
    vector<vector<int>> next = field;

    while(true){
        bool change = false;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(next[i][j] == 0){
                    if((exist(next, i-1, j) && exist(next, i, j-1) && exist(next, i+1, j))
                        || (j + 1 < W && next[i][j+1] == 0 && (different(next, i-1, j, i-1, j+1) || different(next, i-1, j, i-1, j+1)))){
                        if(j + 1 < W && next[i][j+1] == 0 && able(next, i, j) && able(next, i, j+1)){
                            next[i][j] = idx;
                            next[i][j+1] = idx;
                            idx++;
                            change = true;
                            break;
                        }else{
                            return 0;
                        }
                    }
                    if((exist(next, i-1, j) && exist(next, i, j-1) && exist(next, i, j+1))
                        || (i + 1 < H && next[i+1][j] == 0 && (different(next, i, j-1, i+1, j-1) || different(next, i, j+1, i+1, j+1)))){
                        if(i + 1 < H && next[i+1][j] == 0 && able(next, i, j) && able(next, i+1, j)){
                            next[i][j] = idx;
                            next[i+1][j] = idx;
                            idx++;
                            change = true;
                            break;
                        }else{
                            return 0;
                        }
                    }
                }
            }
            if(change) break;
        }
        if(!change) break;
    }

    if(idx == H * W / 2 + 1){
        return 1;
    }

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(next[i][j] == 0){
                assert(i + 1 < H && next[i+1][j] == 0);
                assert(j + 1 < W && next[i][j+1] == 0);
                int ret = 0;
                next[i][j] = idx;
                next[i+1][j] = idx;
                if(able(next, i, j) && able(next, i+1, j)) ret += dfs(next, idx+1);
                next[i+1][j] = 0;
                next[i][j+1] = idx;
                if(able(next, i, j) && able(next, i, j+1)) ret += dfs(next, idx+1);
                return ret;
            }
        }
    }
    assert(false);
    return 0;
}

int main(){
    while(true){
        cin >> H >> W;
        if(H == 0) break;
        vector<vector<int>> field(H, vector<int>(W, 0));
        cout << dfs(field, 1) << endl;
    }

    return 0;
}
### Prompt

Please create a solution in Cpp to the following problem:

A tatami mat, a Japanese traditional floor cover, has a rectangular form with aspect ratio 1:2. When spreading tatami mats on a floor, it is prohibited to make a cross with the border of the tatami mats, because it is believed to bring bad luck.

Your task is to write a program that reports how many possible ways to spread tatami mats of the same size on a floor of given height and width.



Input

The input consists of multiple datasets. Each dataset cosists of a line which contains two integers H and W in this order, separated with a single space. H and W are the height and the width of the floor respectively. The length of the shorter edge of a tatami mat is regarded as a unit length.

You may assume 0 < H, W ≤ 20.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the number of possible ways to spread tatami mats in one line.

Example

Input

3 4
4 4
0 0


Output

4
2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

int H, W;

bool inside(int i, int j){
     return 0 <= i && i < H && 0 <= j && j < W;
}

bool exist(vector<vector<int>>& field, int i, int j){
    return !inside(i, j) || field[i][j] != 0;
}

bool different(vector<vector<int>>& field, int ai, int aj, int bi, int bj){
    return inside(ai, aj) && inside(bi, bj) && field[ai][aj] != 0 && field[bi][bj] != 0 && field[ai][aj] != field[bi][bj];
}

bool able(vector<vector<int>>& field, int i, int j){
    return !(different(field, i-1, j-1, i-1, j) && different(field, i, j-1, i-1, j-1)) && !(different(field, i+1, j-1, i+1, j) && different(field, i+1, j-1, i, j-1));
}

int dfs(vector<vector<int>>& field, int idx){
    vector<vector<int>> next = field;

    while(true){
        bool change = false;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(next[i][j] == 0){
                    if((exist(next, i-1, j) && exist(next, i, j-1) && exist(next, i+1, j))
                        || (j + 1 < W && next[i][j+1] == 0 && (different(next, i-1, j, i-1, j+1) || different(next, i-1, j, i-1, j+1)))){
                        if(j + 1 < W && next[i][j+1] == 0 && able(next, i, j) && able(next, i, j+1)){
                            next[i][j] = idx;
                            next[i][j+1] = idx;
                            idx++;
                            change = true;
                            break;
                        }else{
                            return 0;
                        }
                    }
                    if((exist(next, i-1, j) && exist(next, i, j-1) && exist(next, i, j+1))
                        || (i + 1 < H && next[i+1][j] == 0 && (different(next, i, j-1, i+1, j-1) || different(next, i, j+1, i+1, j+1)))){
                        if(i + 1 < H && next[i+1][j] == 0 && able(next, i, j) && able(next, i+1, j)){
                            next[i][j] = idx;
                            next[i+1][j] = idx;
                            idx++;
                            change = true;
                            break;
                        }else{
                            return 0;
                        }
                    }
                }
            }
            if(change) break;
        }
        if(!change) break;
    }

    if(idx == H * W / 2 + 1){
        return 1;
    }

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(next[i][j] == 0){
                assert(i + 1 < H && next[i+1][j] == 0);
                assert(j + 1 < W && next[i][j+1] == 0);
                int ret = 0;
                next[i][j] = idx;
                next[i+1][j] = idx;
                if(able(next, i, j) && able(next, i+1, j)) ret += dfs(next, idx+1);
                next[i+1][j] = 0;
                next[i][j+1] = idx;
                if(able(next, i, j) && able(next, i, j+1)) ret += dfs(next, idx+1);
                return ret;
            }
        }
    }
    assert(false);
    return 0;
}

int main(){
    while(true){
        cin >> H >> W;
        if(H == 0) break;
        vector<vector<int>> field(H, vector<int>(W, 0));
        cout << dfs(field, 1) << endl;
    }

    return 0;
}
```