#include <cstdio>
#include <cstring>
using namespace std;

int W,H,f[20][20];
int rotx[]={1,0};
int roty[]={0,1};

int cdx[4][4]={
	{-1,-1,0,0},
	{0,0,1,1},
	{-1,-1,0,0},
	{0,0,1,1}
};

int cdy[4][4]={
	{-1,0,-1,0},
	{0,-1,-1,0},
	{0,1,0,1},
	{0,1,0,1}
};

bool check(int x, int y)
{
	for(int j=0; j<4; j++)
	{
		int cnt=0;
		bool ck[400]={0};
		for(int i=0; i<4; i++)
		{
			int tx=x+cdx[j][i], ty=y+cdy[j][i];
			if(tx<0||ty<0||tx>=W||ty>=H) continue;
			if(f[tx][ty]==0) continue;
			if(!ck[f[tx][ty]]) cnt++;
			ck[f[tx][ty]]=1;
		}
		
		if(cnt>3) return false;
	}
	
	return true;
}

int dfs(int x, int y, int ccnt)
{
	if((ccnt-1)*2==W*H) return 1;
	int ret=0;
	bool g=false;
	for(int i=y; i<H; i++)
	{
		for(int j=(i==y?x:0); j<W; j++)
		{
			if(f[j][i]) continue;
			
			g=true;
			for(int k=0; k<2; k++)
			{
				int tx=j+rotx[k], ty=i+roty[k];
				if(tx<0||ty<0||tx>=W||ty>=H) continue;
				if(f[tx][ty]) continue;

				f[j][i]=ccnt;
				f[tx][ty]=ccnt;
				if(check(j,i)) ret+=dfs(j,i,ccnt+1);
				f[j][i]=0;
				f[tx][ty]=0;
				
			}
			
			if(g) break;
		}
		if(g) break;
	}
	
	return ret;
}

int main()
{
	while(scanf("%d%d", &H,&W), (H||W))
	{
		memset(f,0,sizeof(f));
		printf("%d\n", dfs(0,0,1));
	}
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <cstring>
using namespace std;

int W,H,f[20][20];
int rotx[]={1,0};
int roty[]={0,1};

int cdx[4][4]={
	{-1,-1,0,0},
	{0,0,1,1},
	{-1,-1,0,0},
	{0,0,1,1}
};

int cdy[4][4]={
	{-1,0,-1,0},
	{0,-1,-1,0},
	{0,1,0,1},
	{0,1,0,1}
};

bool check(int x, int y)
{
	for(int j=0; j<4; j++)
	{
		int cnt=0;
		bool ck[400]={0};
		for(int i=0; i<4; i++)
		{
			int tx=x+cdx[j][i], ty=y+cdy[j][i];
			if(tx<0||ty<0||tx>=W||ty>=H) continue;
			if(f[tx][ty]==0) continue;
			if(!ck[f[tx][ty]]) cnt++;
			ck[f[tx][ty]]=1;
		}
		
		if(cnt>3) return false;
	}
	
	return true;
}

int dfs(int x, int y, int ccnt)
{
	if((ccnt-1)*2==W*H) return 1;
	int ret=0;
	bool g=false;
	for(int i=y; i<H; i++)
	{
		for(int j=(i==y?x:0); j<W; j++)
		{
			if(f[j][i]) continue;
			
			g=true;
			for(int k=0; k<2; k++)
			{
				int tx=j+rotx[k], ty=i+roty[k];
				if(tx<0||ty<0||tx>=W||ty>=H) continue;
				if(f[tx][ty]) continue;

				f[j][i]=ccnt;
				f[tx][ty]=ccnt;
				if(check(j,i)) ret+=dfs(j,i,ccnt+1);
				f[j][i]=0;
				f[tx][ty]=0;
				
			}
			
			if(g) break;
		}
		if(g) break;
	}
	
	return ret;
}

int main()
{
	while(scanf("%d%d", &H,&W), (H||W))
	{
		memset(f,0,sizeof(f));
		printf("%d\n", dfs(0,0,1));
	}
}
```