#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
ld eps=1e-9;

int H, W;
int dx[4] = { -1,-1,0,0 };
int dy[4] = { -1,0,0,-1 };
bool check(const vector<vector<int>>&v,const int x, const int y) {
	if (!x || !y || x == W || y == H)return true;
	set<int>s;
	for (int i = 0; i < 4; ++i) {
		if (v[y + dy[i]][x + dx[i]]) {
			s.emplace(v[y + dy[i]][x + dx[i]]);
		}
	}
	return s.size() != 4;
}
int getans(vector<vector<int>>&v,const int num) {
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			if (!v[y][x]) {
				int ans = 0;
				v[y][x] = num;
				if(x!=W-1&&!v[y][x+1]){
					v[y][x + 1] = num;
					if (check(v, x, y) && check(v, x + 2, y) && check(v, x + 2, y + 1) && check(v, x, y + 1)) {
						ans += getans(v, num + 1);
					}
					v[y][x + 1] = 0;
				}
				if(y!=H-1){
					v[y+1][x] = num;
					if (check(v, x, y) && check(v, x + 1, y) && check(v, x + 1, y + 2) && check(v, x, y +2)) {
						ans += getans(v, num + 1);
					}
					v[y+1][x] = 0;
				}
				v[y][x] = 0;
				return ans;
			}
		}
	}
	return 1;
}
int main() {
	while (1) { cin >> H >> W;
		if (!H)break;
		vector < vector<int>>v(H, vector<int>(W));
		int ans = getans(v, 1);
		cout << ans << endl;
	}
	return 0;
}
### Prompt

Create a solution in CPP for 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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
ld eps=1e-9;

int H, W;
int dx[4] = { -1,-1,0,0 };
int dy[4] = { -1,0,0,-1 };
bool check(const vector<vector<int>>&v,const int x, const int y) {
	if (!x || !y || x == W || y == H)return true;
	set<int>s;
	for (int i = 0; i < 4; ++i) {
		if (v[y + dy[i]][x + dx[i]]) {
			s.emplace(v[y + dy[i]][x + dx[i]]);
		}
	}
	return s.size() != 4;
}
int getans(vector<vector<int>>&v,const int num) {
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			if (!v[y][x]) {
				int ans = 0;
				v[y][x] = num;
				if(x!=W-1&&!v[y][x+1]){
					v[y][x + 1] = num;
					if (check(v, x, y) && check(v, x + 2, y) && check(v, x + 2, y + 1) && check(v, x, y + 1)) {
						ans += getans(v, num + 1);
					}
					v[y][x + 1] = 0;
				}
				if(y!=H-1){
					v[y+1][x] = num;
					if (check(v, x, y) && check(v, x + 1, y) && check(v, x + 1, y + 2) && check(v, x, y +2)) {
						ans += getans(v, num + 1);
					}
					v[y+1][x] = 0;
				}
				v[y][x] = 0;
				return ans;
			}
		}
	}
	return 1;
}
int main() {
	while (1) { cin >> H >> W;
		if (!H)break;
		vector < vector<int>>v(H, vector<int>(W));
		int ans = getans(v, 1);
		cout << ans << endl;
	}
	return 0;
}
```