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

int H,W;

int used[111][111];

int dx[]={0,0,-1,-1};
int dy[]={0,-1,0,-1};

typedef long long ll;

bool check(int x,int y){
  if( x < 1 || y < 1 ) return true;
  vector<int> p;
  for(int i=0;i<4;i++)
    p.push_back( used[x+dx[i]][y+dy[i]] ); 
  sort(p.begin(),p.end());
  p.erase(unique(p.begin(),p.end()),p.end());

  if( p.size() == 4 ) return false;
  return true;
}

void view(){
  cout << "view" << endl;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout << used[j][i] << " ";
    }
    cout << endl;
  }
}

ll dfs(int x,int y,int cnt){

  if( x >= W ) return dfs(0,y+1,cnt);
  //  view();
  if( y >= H ){
    return 1LL;
  }
  ll res = 0;

  if( used[x][y] == -1 ){
    if( x + 1 < W && used[x+1][y] == -1 ){
      used[x][y] = cnt;
      used[x+1][y] = cnt;
      if( check( x, y ) ){
	res += dfs(x+1,y,cnt+1);
      }
      used[x][y] = -1;
      used[x+1][y] = -1;
    }
    if( y + 1 < H && used[x][y+1] == -1 ){
      used[x][y] = cnt;
      used[x][y+1] = cnt;
      if( check( x, y ) ){
	res += dfs(x+1,y,cnt+1);
      }
      used[x][y] = -1;
      used[x][y+1] = -1;
    }
  } else if( check(x,y) )
      return dfs(x+1,y,cnt);
  
  return res;
}

int main(){
  while( cin >> H >> W &&(W||H) ){
    memset(used,-1,sizeof(used));
    cout << dfs(0,0,0) << endl;
  }
}
### Prompt

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

int H,W;

int used[111][111];

int dx[]={0,0,-1,-1};
int dy[]={0,-1,0,-1};

typedef long long ll;

bool check(int x,int y){
  if( x < 1 || y < 1 ) return true;
  vector<int> p;
  for(int i=0;i<4;i++)
    p.push_back( used[x+dx[i]][y+dy[i]] ); 
  sort(p.begin(),p.end());
  p.erase(unique(p.begin(),p.end()),p.end());

  if( p.size() == 4 ) return false;
  return true;
}

void view(){
  cout << "view" << endl;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout << used[j][i] << " ";
    }
    cout << endl;
  }
}

ll dfs(int x,int y,int cnt){

  if( x >= W ) return dfs(0,y+1,cnt);
  //  view();
  if( y >= H ){
    return 1LL;
  }
  ll res = 0;

  if( used[x][y] == -1 ){
    if( x + 1 < W && used[x+1][y] == -1 ){
      used[x][y] = cnt;
      used[x+1][y] = cnt;
      if( check( x, y ) ){
	res += dfs(x+1,y,cnt+1);
      }
      used[x][y] = -1;
      used[x+1][y] = -1;
    }
    if( y + 1 < H && used[x][y+1] == -1 ){
      used[x][y] = cnt;
      used[x][y+1] = cnt;
      if( check( x, y ) ){
	res += dfs(x+1,y,cnt+1);
      }
      used[x][y] = -1;
      used[x][y+1] = -1;
    }
  } else if( check(x,y) )
      return dfs(x+1,y,cnt);
  
  return res;
}

int main(){
  while( cin >> H >> W &&(W||H) ){
    memset(used,-1,sizeof(used));
    cout << dfs(0,0,0) << endl;
  }
}
```