#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const int dy[][4] = {{0, 0, 1, 1}, {0, 0, 2, 2}};
const int dx[][4] = {{0, 2, 0, 2}, {0, 1, 0, 1}};

int h, w;
vector<vector<bool> > used;
vector<vector<int> > corner;

int solve(int y, int x)
{
    if(x > w){
        ++ y;
        x = 1;
        if(y > h)
            return 1;
    }

    if(used[y][x])
        return solve(y, x+1);

    int ret = 0;
    for(int j=0; j<2; ++j){
        if(!used[y+j][x+(j^1)]){
            bool ok = true;
            used[y][x] = used[y+j][x+(j^1)] = true;
            for(int i=0; i<4; ++i){
                if(++ corner[y+dy[j][i]][x+dx[j][i]] == 4)
                    ok = false;
            }
        
            if(ok)
                ret += solve(y, x+1);

            for(int i=0; i<4; ++i)
                -- corner[y+dy[j][i]][x+dx[j][i]];
            used[y][x] = used[y+j][x+(j^1)] = false;
        }
    }

    return ret;
}

int main()
{
    for(;;){
        cin >> h >> w;
        if(h == 0)
            return 0;

        used.assign(h+2, vector<bool>(w+2, true));
        for(int y=1; y<=h; ++y){
            for(int x=1; x<=w; ++x){
                used[y][x] = false;
            }
        }
        corner.assign(h+2, vector<int>(w+2, 0));

        cout << solve(1, 1) << endl;
    }
}
### Prompt

Develop a solution in Cpp to the problem described below:

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 <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const int dy[][4] = {{0, 0, 1, 1}, {0, 0, 2, 2}};
const int dx[][4] = {{0, 2, 0, 2}, {0, 1, 0, 1}};

int h, w;
vector<vector<bool> > used;
vector<vector<int> > corner;

int solve(int y, int x)
{
    if(x > w){
        ++ y;
        x = 1;
        if(y > h)
            return 1;
    }

    if(used[y][x])
        return solve(y, x+1);

    int ret = 0;
    for(int j=0; j<2; ++j){
        if(!used[y+j][x+(j^1)]){
            bool ok = true;
            used[y][x] = used[y+j][x+(j^1)] = true;
            for(int i=0; i<4; ++i){
                if(++ corner[y+dy[j][i]][x+dx[j][i]] == 4)
                    ok = false;
            }
        
            if(ok)
                ret += solve(y, x+1);

            for(int i=0; i<4; ++i)
                -- corner[y+dy[j][i]][x+dx[j][i]];
            used[y][x] = used[y+j][x+(j^1)] = false;
        }
    }

    return ret;
}

int main()
{
    for(;;){
        cin >> h >> w;
        if(h == 0)
            return 0;

        used.assign(h+2, vector<bool>(w+2, true));
        for(int y=1; y<=h; ++y){
            for(int x=1; x<=w; ++x){
                used[y][x] = false;
            }
        }
        corner.assign(h+2, vector<int>(w+2, 0));

        cout << solve(1, 1) << endl;
    }
}
```