#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define ck(a,b) (0<=a&&a<b)
using namespace std;
int w,h,c,ans,f[20][20];
bool crs(int y1,int x1,int y2,int x2){
	for(int y=y1;y<y2;y++)for(int x=x1;x<x2;x++)if(ck(y,h)&&ck(y+1,h)&&ck(x,w)&&ck(x+1,w)&&
		f[y][x]!=f[y][x+1]&&f[y][x]!=f[y+1][x]&&f[y][x]!=f[y+1][x+1]&&
		f[y][x+1]!=f[y+1][x]&&f[y][x+1]!=f[y+1][x+1]&&f[y+1][x]!=f[y+1][x+1])return 1;
	return 0;
}
void dfs(int y,int x){
	for(;y<h&&(x>=w||f[y][x]);x++)if(x>=w)x=-1,y++;
	if(y>=h&&c*2==w*h){
		ans++;return;
	}
	if(ck(x+1,w)&&!f[y][x]&&!f[y][x+1]){
		f[y][x]=f[y][x+1]=++c;
		if(!crs(y-1,x-1,y+1,x+2))dfs(y,x+2);
		f[y][x]=f[y][x+1]=0;--c;
	}
	if(ck(y+1,h)&&!f[y][x]&&!f[y+1][x]){
		f[y][x]=f[y+1][x]=++c;
		if(!crs(y-1,x-1,y+2,x+1))dfs(y,x+1);
		f[y][x]=f[y+1][x]=0;--c;
	}
}
int main(){
	while(cin>>w>>h,w){
		c=ans=0;
		rep(i,h)rep(j,w)f[i][j]=0;
		dfs(0,0);
		cout<<ans<<endl;
	}
	return 0;
}
### Prompt

Please provide a cpp coded solution 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<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define ck(a,b) (0<=a&&a<b)
using namespace std;
int w,h,c,ans,f[20][20];
bool crs(int y1,int x1,int y2,int x2){
	for(int y=y1;y<y2;y++)for(int x=x1;x<x2;x++)if(ck(y,h)&&ck(y+1,h)&&ck(x,w)&&ck(x+1,w)&&
		f[y][x]!=f[y][x+1]&&f[y][x]!=f[y+1][x]&&f[y][x]!=f[y+1][x+1]&&
		f[y][x+1]!=f[y+1][x]&&f[y][x+1]!=f[y+1][x+1]&&f[y+1][x]!=f[y+1][x+1])return 1;
	return 0;
}
void dfs(int y,int x){
	for(;y<h&&(x>=w||f[y][x]);x++)if(x>=w)x=-1,y++;
	if(y>=h&&c*2==w*h){
		ans++;return;
	}
	if(ck(x+1,w)&&!f[y][x]&&!f[y][x+1]){
		f[y][x]=f[y][x+1]=++c;
		if(!crs(y-1,x-1,y+1,x+2))dfs(y,x+2);
		f[y][x]=f[y][x+1]=0;--c;
	}
	if(ck(y+1,h)&&!f[y][x]&&!f[y+1][x]){
		f[y][x]=f[y+1][x]=++c;
		if(!crs(y-1,x-1,y+2,x+1))dfs(y,x+1);
		f[y][x]=f[y+1][x]=0;--c;
	}
}
int main(){
	while(cin>>w>>h,w){
		c=ans=0;
		rep(i,h)rep(j,w)f[i][j]=0;
		dfs(0,0);
		cout<<ans<<endl;
	}
	return 0;
}
```