#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct data{
	int fie[23][23];
	bool dir[23][23][4];
	int cnt[23][23];
};

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int h,w;
int fie[23][23];
bool dir[23][23][4];
int cnt[23][23];
int ans=0;

stack<data> sta;

void push(){
	data dat;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			dat.fie[i][j]=fie[i][j];
			dat.cnt[i][j]=cnt[i][j];
			for(int k=0;k<4;k++){
				dat.dir[i][j][k]=dir[i][j][k];
			}
		}
	}
	sta.push(dat);
}

void pop(){
	data dat=sta.top();
	sta.pop();
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			fie[i][j]=dat.fie[i][j];
			cnt[i][j]=dat.cnt[i][j];
			for(int k=0;k<4;k++){
				dir[i][j][k]=dat.dir[i][j][k];
			}
		}
	}
}

void check(int y,int x){
	if(y<0 || y>=h || x<0 || x>=w)return;
	for(int i=0;i<4;i++){
		if(dir[y][x][i])continue;
		if(fie[y][x] || fie[y+dy[i]][x+dx[i]]){
			dir[y][x][i]=true;
			cnt[y][x]++;
		}
	}
}

void dfs(int c){
	if(c*2==h*w){
		ans++;
		return;
	}
	int nx=0,ny=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(fie[i][j])continue;
			if(cnt[i][j]==4 && !fie[i][j])return;
			if(fie[ny][nx] || cnt[ny][nx]<cnt[i][j]){
				ny=i;
				nx=j;
			}
		}
	}
	if(fie[ny][nx] || cnt[ny][nx]==4)return;
	for(int i=0;i<4;i++){
		if(dir[ny][nx][i])continue;
		push();
		fie[ny][nx]=c+1;
		fie[ny+dy[i]][nx+dx[i]]=c+1;
		for(int j=ny-2;j<=ny+2;j++){
			for(int k=nx-2;k<=nx+2;k++){
				check(j,k);
			}
		}
		if(i%2==1){
			if(i>=2)nx--;
			if(ny-1>=0 && nx-1>=0){
				if(!dir[ny-1][nx-1][2]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx-1][0]){
						cnt[ny-2][nx-1]++;
					}
					dir[ny-2][nx-1][0]=true;
				}
				if(!dir[ny-1][nx-1][3]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny-1][nx-2][1]){
						cnt[ny-1][nx-2]++;
					}
					dir[ny-1][nx-2][1]=true;
				}
			}
			if(ny-1>=0){
				if(!dir[ny-1][nx+2][2]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx+2][0]){
						cnt[ny-2][nx+2]++;
					}
					dir[ny-2][nx+2][0]=true;
				}
				if(!dir[ny-1][nx+2][1]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][1]=true;

				if(!dir[ny-1][nx+3][3]){
					cnt[ny-1][nx+3]++;
				}
				dir[ny-1][nx+3][3]=true;
			}
			if(nx-1>=0){
				if(!dir[ny+1][nx-1][0]){
					cnt[ny+1][nx-1]++;
				}
				dir[ny+1][nx-1][0]=true;
				if(!dir[ny+2][nx-1][2]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][2]=true;

				if(!dir[ny+1][nx-1][3]){
					cnt[ny+1][nx-1]++;
				}
				dir[ny+1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny+1][nx-2][1]){
						cnt[ny+1][nx-2]++;
					}
					dir[ny+1][nx-2][1]=true;
				}
			}
			if(!dir[ny+1][nx+2][0]){
				cnt[ny+1][nx+2]++;
			}
			dir[ny+1][nx+2][0]=true;
			if(!dir[ny+2][nx+2][2]){
				cnt[ny+2][nx+2]++;
			}
			dir[ny+2][nx+2][2]=true;
			if(!dir[ny+1][nx+2][1]){
				cnt[ny+1][nx+2]++;
			}
			dir[ny+1][nx+2][1]=true;
			if(!dir[ny+1][nx+3][3]){
				cnt[ny+1][nx+3]++;
			}
			dir[ny+1][nx+3][3]=true;
		}else{
			if(i>=2)ny--;
			if(ny-1>=0 && nx-1>=0){
				if(!dir[ny-1][nx-1][2]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx-1][0]){
						cnt[ny-2][nx-1]++;
					}
					dir[ny-2][nx-1][0]=true;
				}
				if(!dir[ny-1][nx-1][3]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny-1][nx-2][1]){
						cnt[ny-1][nx-2]++;
					}
					dir[ny-1][nx-2][1]=true;
				}
			}
			if(ny-1>=0){
				if(!dir[ny-1][nx+1][2]){
					cnt[ny-1][nx+1]++;
				}
				dir[ny-1][nx+1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx+1][0]){
						cnt[ny-2][nx+1]++;
					}
					dir[ny-2][nx+1][0]=true;
				}
				if(!dir[ny-1][nx+1][1]){
					cnt[ny-1][nx+1]++;
				}
				dir[ny-1][nx+1][1]=true;

				if(!dir[ny-1][nx+2][3]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][3]=true;
			}
			if(nx-1>=0){
				if(!dir[ny+2][nx-1][0]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][0]=true;
				if(!dir[ny+3][nx-1][2]){
					cnt[ny+3][nx-1]++;
				}
				dir[ny+3][nx-1][2]=true;

				if(!dir[ny+2][nx-1][3]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny+2][nx-2][1]){
						cnt[ny+2][nx-2]++;
					}
					dir[ny+2][nx-2][1]=true;
				}
			}
			if(!dir[ny+2][nx+1][0]){
				cnt[ny+2][nx+1]++;
			}
			dir[ny+2][nx+1][0]=true;
			if(!dir[ny+3][nx+1][2]){
				cnt[ny+3][nx+1]++;
			}
			dir[ny+3][nx+1][2]=true;
			if(!dir[ny+2][nx+1][1]){
				cnt[ny+2][nx+1]++;
			}
			dir[ny+2][nx+1][1]=true;
			if(!dir[ny+2][nx+2][3]){
				cnt[ny+2][nx+2]++;
			}
			dir[ny+2][nx+2][3]=true;
		}
		dfs(c+1);
		pop();
	}
}


void solve(){
	if(h*w%2==1){
		printf("0\n");
		return;
	}
	ans=0;
	memset(fie,false,sizeof(fie));
	memset(dir,false,sizeof(dir));
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<h;i++){
		cnt[i][0]++;
		dir[i][0][3]=true;
		cnt[i][w-1]++;
		dir[i][w-1][1]=true;
	}
	for(int i=0;i<w;i++){
		cnt[0][i]++;
		dir[0][i][2]=true;
		cnt[h-1][i]++;
		dir[h-1][i][0]=true;
	}
	dfs(0);
	printf("%d\n",ans);
}

int main(void){
	while(1){
		scanf("%d%d",&h,&w);
		if(h==0 && w==0)return 0;
		solve();
	}
	return 0;
}

### Prompt

Your task is to create a CPP solution to 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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct data{
	int fie[23][23];
	bool dir[23][23][4];
	int cnt[23][23];
};

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int h,w;
int fie[23][23];
bool dir[23][23][4];
int cnt[23][23];
int ans=0;

stack<data> sta;

void push(){
	data dat;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			dat.fie[i][j]=fie[i][j];
			dat.cnt[i][j]=cnt[i][j];
			for(int k=0;k<4;k++){
				dat.dir[i][j][k]=dir[i][j][k];
			}
		}
	}
	sta.push(dat);
}

void pop(){
	data dat=sta.top();
	sta.pop();
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			fie[i][j]=dat.fie[i][j];
			cnt[i][j]=dat.cnt[i][j];
			for(int k=0;k<4;k++){
				dir[i][j][k]=dat.dir[i][j][k];
			}
		}
	}
}

void check(int y,int x){
	if(y<0 || y>=h || x<0 || x>=w)return;
	for(int i=0;i<4;i++){
		if(dir[y][x][i])continue;
		if(fie[y][x] || fie[y+dy[i]][x+dx[i]]){
			dir[y][x][i]=true;
			cnt[y][x]++;
		}
	}
}

void dfs(int c){
	if(c*2==h*w){
		ans++;
		return;
	}
	int nx=0,ny=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(fie[i][j])continue;
			if(cnt[i][j]==4 && !fie[i][j])return;
			if(fie[ny][nx] || cnt[ny][nx]<cnt[i][j]){
				ny=i;
				nx=j;
			}
		}
	}
	if(fie[ny][nx] || cnt[ny][nx]==4)return;
	for(int i=0;i<4;i++){
		if(dir[ny][nx][i])continue;
		push();
		fie[ny][nx]=c+1;
		fie[ny+dy[i]][nx+dx[i]]=c+1;
		for(int j=ny-2;j<=ny+2;j++){
			for(int k=nx-2;k<=nx+2;k++){
				check(j,k);
			}
		}
		if(i%2==1){
			if(i>=2)nx--;
			if(ny-1>=0 && nx-1>=0){
				if(!dir[ny-1][nx-1][2]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx-1][0]){
						cnt[ny-2][nx-1]++;
					}
					dir[ny-2][nx-1][0]=true;
				}
				if(!dir[ny-1][nx-1][3]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny-1][nx-2][1]){
						cnt[ny-1][nx-2]++;
					}
					dir[ny-1][nx-2][1]=true;
				}
			}
			if(ny-1>=0){
				if(!dir[ny-1][nx+2][2]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx+2][0]){
						cnt[ny-2][nx+2]++;
					}
					dir[ny-2][nx+2][0]=true;
				}
				if(!dir[ny-1][nx+2][1]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][1]=true;

				if(!dir[ny-1][nx+3][3]){
					cnt[ny-1][nx+3]++;
				}
				dir[ny-1][nx+3][3]=true;
			}
			if(nx-1>=0){
				if(!dir[ny+1][nx-1][0]){
					cnt[ny+1][nx-1]++;
				}
				dir[ny+1][nx-1][0]=true;
				if(!dir[ny+2][nx-1][2]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][2]=true;

				if(!dir[ny+1][nx-1][3]){
					cnt[ny+1][nx-1]++;
				}
				dir[ny+1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny+1][nx-2][1]){
						cnt[ny+1][nx-2]++;
					}
					dir[ny+1][nx-2][1]=true;
				}
			}
			if(!dir[ny+1][nx+2][0]){
				cnt[ny+1][nx+2]++;
			}
			dir[ny+1][nx+2][0]=true;
			if(!dir[ny+2][nx+2][2]){
				cnt[ny+2][nx+2]++;
			}
			dir[ny+2][nx+2][2]=true;
			if(!dir[ny+1][nx+2][1]){
				cnt[ny+1][nx+2]++;
			}
			dir[ny+1][nx+2][1]=true;
			if(!dir[ny+1][nx+3][3]){
				cnt[ny+1][nx+3]++;
			}
			dir[ny+1][nx+3][3]=true;
		}else{
			if(i>=2)ny--;
			if(ny-1>=0 && nx-1>=0){
				if(!dir[ny-1][nx-1][2]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx-1][0]){
						cnt[ny-2][nx-1]++;
					}
					dir[ny-2][nx-1][0]=true;
				}
				if(!dir[ny-1][nx-1][3]){
					cnt[ny-1][nx-1]++;
				}
				dir[ny-1][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny-1][nx-2][1]){
						cnt[ny-1][nx-2]++;
					}
					dir[ny-1][nx-2][1]=true;
				}
			}
			if(ny-1>=0){
				if(!dir[ny-1][nx+1][2]){
					cnt[ny-1][nx+1]++;
				}
				dir[ny-1][nx+1][2]=true;
				if(ny-2>=0){
					if(!dir[ny-2][nx+1][0]){
						cnt[ny-2][nx+1]++;
					}
					dir[ny-2][nx+1][0]=true;
				}
				if(!dir[ny-1][nx+1][1]){
					cnt[ny-1][nx+1]++;
				}
				dir[ny-1][nx+1][1]=true;

				if(!dir[ny-1][nx+2][3]){
					cnt[ny-1][nx+2]++;
				}
				dir[ny-1][nx+2][3]=true;
			}
			if(nx-1>=0){
				if(!dir[ny+2][nx-1][0]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][0]=true;
				if(!dir[ny+3][nx-1][2]){
					cnt[ny+3][nx-1]++;
				}
				dir[ny+3][nx-1][2]=true;

				if(!dir[ny+2][nx-1][3]){
					cnt[ny+2][nx-1]++;
				}
				dir[ny+2][nx-1][3]=true;
				if(nx-2>=0){
					if(!dir[ny+2][nx-2][1]){
						cnt[ny+2][nx-2]++;
					}
					dir[ny+2][nx-2][1]=true;
				}
			}
			if(!dir[ny+2][nx+1][0]){
				cnt[ny+2][nx+1]++;
			}
			dir[ny+2][nx+1][0]=true;
			if(!dir[ny+3][nx+1][2]){
				cnt[ny+3][nx+1]++;
			}
			dir[ny+3][nx+1][2]=true;
			if(!dir[ny+2][nx+1][1]){
				cnt[ny+2][nx+1]++;
			}
			dir[ny+2][nx+1][1]=true;
			if(!dir[ny+2][nx+2][3]){
				cnt[ny+2][nx+2]++;
			}
			dir[ny+2][nx+2][3]=true;
		}
		dfs(c+1);
		pop();
	}
}


void solve(){
	if(h*w%2==1){
		printf("0\n");
		return;
	}
	ans=0;
	memset(fie,false,sizeof(fie));
	memset(dir,false,sizeof(dir));
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<h;i++){
		cnt[i][0]++;
		dir[i][0][3]=true;
		cnt[i][w-1]++;
		dir[i][w-1][1]=true;
	}
	for(int i=0;i<w;i++){
		cnt[0][i]++;
		dir[0][i][2]=true;
		cnt[h-1][i]++;
		dir[h-1][i][0]=true;
	}
	dfs(0);
	printf("%d\n",ans);
}

int main(void){
	while(1){
		scanf("%d%d",&h,&w);
		if(h==0 && w==0)return 0;
		solve();
	}
	return 0;
}

```