#include <bits/stdc++.h>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

bool corner(vvi& grid,int i,int j)
{
	return i>0 && j>0 && grid[i-1][j-1]!=grid[i-1][j] && grid[i-1][j-1]!=grid[i][j-1];
}

int check(vvi& grid,int i,int j)
{
	int h=grid.size(),w=grid[0].size(),res=0;
	if(0<=i && i<h && 0<=j && j+1<w && grid[i][j]==-1 && grid[i][j+1]==-1 && !corner(grid,i,j))
		res|=1;
	if(0<=i && i+1<h && 0<=j && j<w && grid[i][j]==-1 && grid[i+1][j]==-1 && !corner(grid,i,j))
		res|=2;
	return res;
}

int dfs(vvi& grid,int i,int j,int cnt)
{
	int h=grid.size(),w=grid[0].size();
	if(cnt*2==h*w) return 1;
	if(j==w) i++,j=0;
	if(i==h) return 0;
	if(grid[i][j]!=-1) return dfs(grid,i,j+1,cnt);
	
	int flg=check(grid,i,j),res=0;
	// 横
	if(flg&1){
		grid[i][j]=grid[i][j+1]=cnt;
		res+=dfs(grid,i,j+1,cnt+1);
		grid[i][j]=grid[i][j+1]=-1;
	}
	// 縦
	if(flg&2){
		grid[i][j]=grid[i+1][j]=cnt;
		res+=dfs(grid,i,j+1,cnt+1);
		grid[i][j]=grid[i+1][j]=-1;
	}
	return res;
}

int main()
{
	for(int h,w;cin>>h>>w && h|w;){
		vvi grid(h,vi(w,-1));
		cout<<dfs(grid,0,0,0)<<endl;
	}
}
### 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>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

bool corner(vvi& grid,int i,int j)
{
	return i>0 && j>0 && grid[i-1][j-1]!=grid[i-1][j] && grid[i-1][j-1]!=grid[i][j-1];
}

int check(vvi& grid,int i,int j)
{
	int h=grid.size(),w=grid[0].size(),res=0;
	if(0<=i && i<h && 0<=j && j+1<w && grid[i][j]==-1 && grid[i][j+1]==-1 && !corner(grid,i,j))
		res|=1;
	if(0<=i && i+1<h && 0<=j && j<w && grid[i][j]==-1 && grid[i+1][j]==-1 && !corner(grid,i,j))
		res|=2;
	return res;
}

int dfs(vvi& grid,int i,int j,int cnt)
{
	int h=grid.size(),w=grid[0].size();
	if(cnt*2==h*w) return 1;
	if(j==w) i++,j=0;
	if(i==h) return 0;
	if(grid[i][j]!=-1) return dfs(grid,i,j+1,cnt);
	
	int flg=check(grid,i,j),res=0;
	// 横
	if(flg&1){
		grid[i][j]=grid[i][j+1]=cnt;
		res+=dfs(grid,i,j+1,cnt+1);
		grid[i][j]=grid[i][j+1]=-1;
	}
	// 縦
	if(flg&2){
		grid[i][j]=grid[i+1][j]=cnt;
		res+=dfs(grid,i,j+1,cnt+1);
		grid[i][j]=grid[i+1][j]=-1;
	}
	return res;
}

int main()
{
	for(int h,w;cin>>h>>w && h|w;){
		vvi grid(h,vi(w,-1));
		cout<<dfs(grid,0,0,0)<<endl;
	}
}
```