#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int h,w;
int used[21][21];
int mn=0;

void dfs(int cur,int num){
	if(cur==h*w){
		mn++;
		return;
	}
	int curh=cur/w;
	int curw=cur%w;
	if(used[curh][curw]!=-1){
		dfs(cur+1,num);
		return;
	}
	// ツ可。ツづ可静敖置
	if(curw+1<w&&used[curh][curw+1]==-1){
		if(!(curw+2<w&&curh>=1&&used[curh-1][curw+1]!=used[curh-1][curw+2]&&used[curh][curw+2]==-1)){
			used[curh][curw]=num;
			used[curh][curw+1]=num;
			dfs(cur+1,num+1);
			used[curh][curw]=-1;
			used[curh][curw+1]=-1;
		}
	}
	// ツ縦ツづ可静敖置
	if(curh+1<h&&used[curh+1][curw]==-1){
		if(!(curw+1<w&&curh>=1&&used[curh-1][curw+1]!=used[curh-1][curw]&&used[curh][curw+1]==-1)){
			used[curh][curw]=num;
			used[curh+1][curw]=num;
			dfs(cur+1,num+1);
			used[curh][curw]=-1;
			used[curh+1][curw]=-1;
		}
	}
}

int main(){

	while(cin>>h>>w&&(h|w)){
		mn=0;
		memset(used,-1,sizeof(used));
		dfs(0,0);
		cout<<mn<<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 <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int h,w;
int used[21][21];
int mn=0;

void dfs(int cur,int num){
	if(cur==h*w){
		mn++;
		return;
	}
	int curh=cur/w;
	int curw=cur%w;
	if(used[curh][curw]!=-1){
		dfs(cur+1,num);
		return;
	}
	// ツ可。ツづ可静敖置
	if(curw+1<w&&used[curh][curw+1]==-1){
		if(!(curw+2<w&&curh>=1&&used[curh-1][curw+1]!=used[curh-1][curw+2]&&used[curh][curw+2]==-1)){
			used[curh][curw]=num;
			used[curh][curw+1]=num;
			dfs(cur+1,num+1);
			used[curh][curw]=-1;
			used[curh][curw+1]=-1;
		}
	}
	// ツ縦ツづ可静敖置
	if(curh+1<h&&used[curh+1][curw]==-1){
		if(!(curw+1<w&&curh>=1&&used[curh-1][curw+1]!=used[curh-1][curw]&&used[curh][curw+1]==-1)){
			used[curh][curw]=num;
			used[curh+1][curw]=num;
			dfs(cur+1,num+1);
			used[curh][curw]=-1;
			used[curh+1][curw]=-1;
		}
	}
}

int main(){

	while(cin>>h>>w&&(h|w)){
		mn=0;
		memset(used,-1,sizeof(used));
		dfs(0,0);
		cout<<mn<<endl;
	}

	return 0;
}
```