#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cassert>
#include<climits>
#include<iomanip>
#define F first
#define S second
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<int,bool> IB;
int H,W;
int cnt;
int dx[] = {+0,+0,+1};
int dy[] = {+1,-1,+0};
map<VVI,int> hope;

P pdx[] = {P(0,1),P(0,0)};
P pdy[] = {P(0,0),P(0,1)};
int tdx[2][6] = {{+0,+1,+1,+1,+0,-1},{+0,-1,-1,+0,+1,+1}};
int tdy[2][6] = {{+0,+0,+1,+2,+2,+1},{+0,+1,+3,+4,+3,+1}};

vector<P> PtoVec(P p)
{
  vector<P> vec(4);
  vec[0] = P(p.F,p.S*2-1);//top
  vec[1] = P(p.F,p.S*2+1);//bottom
  vec[2] = P(p.F-1,p.S*2);//left
  vec[3] = P(p.F+0,p.S*2);//right
  return vec;
}

vector<P> Union(vector<P> p1,vector<P> p2)
{
  vector<P> p3;
  map<P,bool> exist;
  rep(i,4)
      exist[p1[i]] = true;

  bool ok = false;
  rep(i,4)
    {
      if(exist[p2[i]])
	{
	  ok = true;
	  exist[p2[i]] = false;
	  continue;
	}
      exist[p2[i]] = true;    
    }
  assert(ok);
  rep(i,4)
    {
      if(exist[p1[i]])
	p3.push_back(p1[i]);
      if(exist[p2[i]])
	p3.push_back(p2[i]);
    }
  return p3;
}

void drawTatamiKai(VVI &tatami,vector<P> p3)
{
  rep(i,6)
    {
      if(!(0 <= p3[i].F && p3[i].F < W && 0 <= p3[i].S && p3[i].S <= H+(H-2))) continue;
      tatami[p3[i].S][p3[i].F] = 1;
    }
}

void eraseTatamiKai(VVI &tatami,vector<P> p3)
{
  rep(i,6)
    {
      if(!(0 <= p3[i].F && p3[i].F < W && 0 <= p3[i].S && p3[i].S <= H+(H-2))) continue;
      tatami[p3[i].S][p3[i].F] = 0;
    }
}

bool check1(VVI &G)// finish check
{
  rep(i,H)
    rep(j,W)
      if(G[i][j] == 0)
	return false;

  return true;
}

bool check2(VVI &tatami)//cross check
{
 
  rep(i,H+(H-2)+1)
    rep(j,W)
    {
        if(!tatami[i][j])continue;
        if(i%2 == 0)continue;
        if(!tatami[i][j])continue;
	//cout << j << " - " << i << endl;
     
	  int counter = 0;
	  rep(l,3)
	    {
	      int nx = j+dx[l];
	      int ny = i+dy[l];
	      if(!(0 <= nx && nx < W && 0 <= ny && ny <= H+(H-2)))continue;
	      if(tatami[ny][nx])counter++;
	      else break;
	    }
	  if(counter == 3)
	    return false;
	  //cout << "counter = "<< counter << endl;
	
    }
  return true;
}

bool check3(VVI &G,int x,int y,int type)
{
  int nx1 = x + pdx[type].F;
  int ny1 = y + pdy[type].F;
  if(!(0 <= nx1 && nx1 < W && 0 <= ny1 && ny1 < H))return false;
  if(G[ny1][nx1])return false;
  
  int nx2 = x + pdx[type].S;
  int ny2 = y + pdy[type].S;
  if(!(0 <= nx2 && nx2 < W && 0 <= ny2 && ny2 < H))return false;
  if(G[ny2][nx2])return false;
    
  return true;
}

void next(int &x,int &y)
{
  x++;
  if(x >= W)
    x = 0,y++;
}

void dfs(VVI &G,VVI &tatami,int x,int y,int dc)
{  
  //cout << x << " " <<y << endl;
  if( dc < y*W+x)return;
  if(x >= W-1 && y >= H-1)
    {
      if(dc != W*H)return;
      //if(!check1(G))return;
      if(!check2(tatami))return;
      cnt++;
      return;
    }
 
  if(G[y][x])
    {
      next(x,y);
      dfs(G,tatami,x,y,dc);
      return;
    }
  if(!check2(tatami))return;

  for(int i=0;i<2;i++)
    {
      if(!(check3(G,x,y,i)))continue;
      int nx1 = x + pdx[i].F;
      int ny1 = y + pdy[i].F;
     
      int nx2 = x + pdx[i].S;
      int ny2 = y + pdy[i].S;
     
      //assert(!G[ny1][nx1]);
      //assert(!G[ny2][nx2]);
      G[ny1][nx1] = 1;
      G[ny2][nx2] = 1;
      vector<P> p3;
      if(1)
	{
	  vector<P> p1 = PtoVec(P(nx1,ny1));
	  vector<P> p2 = PtoVec(P(nx2,ny2));
	  p3 = Union(p1,p2);
	}
      drawTatamiKai(tatami,p3);
      int cpx,cpy;
      cpx = x,cpy = y;
      next(cpx,cpy);
      
      dfs(G,tatami,cpx,cpy,dc+2);
      eraseTatamiKai(tatami,p3);
      G[ny1][nx1] = 0;
      G[ny2][nx2] = 0;
    }
}

 
int main()
{  
  map<P,int> umekomi;
  umekomi[P(20,20)] = umekomi[P(20,20)] = 2;
  umekomi[P(20,19)] = umekomi[P(19,20)] = 2;
  umekomi[P(20,18)] = umekomi[P(18,20)] = 1;
  umekomi[P(20,17)] = umekomi[P(17,20)] = 0;
  umekomi[P(20,16)] = umekomi[P(16,20)] = 0;
  umekomi[P(20,15)] = umekomi[P(15,20)] = 0;
  umekomi[P(20,14)] = umekomi[P(14,20)] = 0;
  umekomi[P(20,13)] = umekomi[P(13,20)] = 0;
  umekomi[P(20,12)] = umekomi[P(12,20)] = 0;
  umekomi[P(20,11)] = umekomi[P(11,20)] = 2;
  umekomi[P(19,18)] = umekomi[P(18,19)] = 2;
  umekomi[P(19,16)] = umekomi[P(16,19)] = 0;
  umekomi[P(19,14)] = umekomi[P(14,19)] = 0;
  umekomi[P(19,12)] = umekomi[P(12,19)] = 0;
  umekomi[P(18,18)] = umekomi[P(18,18)] = 2;
  umekomi[P(18,17)] = umekomi[P(17,18)] = 2;
  umekomi[P(18,16)] = umekomi[P(16,18)] = 1;
  umekomi[P(18,15)] = umekomi[P(15,18)] = 0;
  umekomi[P(18,14)] = umekomi[P(14,18)] = 0;
  umekomi[P(18,13)] = umekomi[P(13,18)] = 0;
  umekomi[P(18,12)] = umekomi[P(12,18)] = 0;
  umekomi[P(18,11)] = umekomi[P(11,18)] = 0;
  umekomi[P(17,16)] = umekomi[P(16,17)] = 2;
  umekomi[P(17,14)] = umekomi[P(14,17)] = 0;
  umekomi[P(16,16)] = umekomi[P(16,16)] = 2;
  umekomi[P(16,15)] = umekomi[P(15,16)] = 2;
  umekomi[P(16,14)] = umekomi[P(14,16)] = 1;
  umekomi[P(16,13)] = umekomi[P(13,16)] = 0;
  umekomi[P(15,14)] = umekomi[P(14,15)] = 2;
  umekomi[P(15,12)] = umekomi[P(12,15)] = 0;

  while(cin >> H >> W,H|W)
    {
      if((H*W)%2 != 0)
	{
	  cout << 0 << endl;
	  continue;
	}
      //clock_t st,ed;
      //st = clock();
      if(umekomi.find(P(H,W)) != umekomi.end())
	{
	  cout << umekomi[P(H,W)] << endl;
	  continue;
	}
      cnt = 0;
      VVI G(H,VI(W,0));
      VVI tatami(H+(H-2)+1,VI(W,0));
      dfs(G,tatami,0,0,0);
      cout << cnt << endl;
      //cout << "umekomi[P("<<H<<","<<W<<")] = umekomi[P("<<W<<","<<H<<")] = " << cnt  << ";"<< endl;
      //cout << cnt << endl;
      umekomi[P(H,W)] = umekomi[P(W,H)] = cnt;
      //ed = clock();
      //cout << setiosflags(ios::fixed) << setprecision(10) << (double)(ed-st)/CLOCKS_PER_SEC << endl;
    }
  return 0;
}
### Prompt

Your challenge is to write 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<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cassert>
#include<climits>
#include<iomanip>
#define F first
#define S second
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<int,bool> IB;
int H,W;
int cnt;
int dx[] = {+0,+0,+1};
int dy[] = {+1,-1,+0};
map<VVI,int> hope;

P pdx[] = {P(0,1),P(0,0)};
P pdy[] = {P(0,0),P(0,1)};
int tdx[2][6] = {{+0,+1,+1,+1,+0,-1},{+0,-1,-1,+0,+1,+1}};
int tdy[2][6] = {{+0,+0,+1,+2,+2,+1},{+0,+1,+3,+4,+3,+1}};

vector<P> PtoVec(P p)
{
  vector<P> vec(4);
  vec[0] = P(p.F,p.S*2-1);//top
  vec[1] = P(p.F,p.S*2+1);//bottom
  vec[2] = P(p.F-1,p.S*2);//left
  vec[3] = P(p.F+0,p.S*2);//right
  return vec;
}

vector<P> Union(vector<P> p1,vector<P> p2)
{
  vector<P> p3;
  map<P,bool> exist;
  rep(i,4)
      exist[p1[i]] = true;

  bool ok = false;
  rep(i,4)
    {
      if(exist[p2[i]])
	{
	  ok = true;
	  exist[p2[i]] = false;
	  continue;
	}
      exist[p2[i]] = true;    
    }
  assert(ok);
  rep(i,4)
    {
      if(exist[p1[i]])
	p3.push_back(p1[i]);
      if(exist[p2[i]])
	p3.push_back(p2[i]);
    }
  return p3;
}

void drawTatamiKai(VVI &tatami,vector<P> p3)
{
  rep(i,6)
    {
      if(!(0 <= p3[i].F && p3[i].F < W && 0 <= p3[i].S && p3[i].S <= H+(H-2))) continue;
      tatami[p3[i].S][p3[i].F] = 1;
    }
}

void eraseTatamiKai(VVI &tatami,vector<P> p3)
{
  rep(i,6)
    {
      if(!(0 <= p3[i].F && p3[i].F < W && 0 <= p3[i].S && p3[i].S <= H+(H-2))) continue;
      tatami[p3[i].S][p3[i].F] = 0;
    }
}

bool check1(VVI &G)// finish check
{
  rep(i,H)
    rep(j,W)
      if(G[i][j] == 0)
	return false;

  return true;
}

bool check2(VVI &tatami)//cross check
{
 
  rep(i,H+(H-2)+1)
    rep(j,W)
    {
        if(!tatami[i][j])continue;
        if(i%2 == 0)continue;
        if(!tatami[i][j])continue;
	//cout << j << " - " << i << endl;
     
	  int counter = 0;
	  rep(l,3)
	    {
	      int nx = j+dx[l];
	      int ny = i+dy[l];
	      if(!(0 <= nx && nx < W && 0 <= ny && ny <= H+(H-2)))continue;
	      if(tatami[ny][nx])counter++;
	      else break;
	    }
	  if(counter == 3)
	    return false;
	  //cout << "counter = "<< counter << endl;
	
    }
  return true;
}

bool check3(VVI &G,int x,int y,int type)
{
  int nx1 = x + pdx[type].F;
  int ny1 = y + pdy[type].F;
  if(!(0 <= nx1 && nx1 < W && 0 <= ny1 && ny1 < H))return false;
  if(G[ny1][nx1])return false;
  
  int nx2 = x + pdx[type].S;
  int ny2 = y + pdy[type].S;
  if(!(0 <= nx2 && nx2 < W && 0 <= ny2 && ny2 < H))return false;
  if(G[ny2][nx2])return false;
    
  return true;
}

void next(int &x,int &y)
{
  x++;
  if(x >= W)
    x = 0,y++;
}

void dfs(VVI &G,VVI &tatami,int x,int y,int dc)
{  
  //cout << x << " " <<y << endl;
  if( dc < y*W+x)return;
  if(x >= W-1 && y >= H-1)
    {
      if(dc != W*H)return;
      //if(!check1(G))return;
      if(!check2(tatami))return;
      cnt++;
      return;
    }
 
  if(G[y][x])
    {
      next(x,y);
      dfs(G,tatami,x,y,dc);
      return;
    }
  if(!check2(tatami))return;

  for(int i=0;i<2;i++)
    {
      if(!(check3(G,x,y,i)))continue;
      int nx1 = x + pdx[i].F;
      int ny1 = y + pdy[i].F;
     
      int nx2 = x + pdx[i].S;
      int ny2 = y + pdy[i].S;
     
      //assert(!G[ny1][nx1]);
      //assert(!G[ny2][nx2]);
      G[ny1][nx1] = 1;
      G[ny2][nx2] = 1;
      vector<P> p3;
      if(1)
	{
	  vector<P> p1 = PtoVec(P(nx1,ny1));
	  vector<P> p2 = PtoVec(P(nx2,ny2));
	  p3 = Union(p1,p2);
	}
      drawTatamiKai(tatami,p3);
      int cpx,cpy;
      cpx = x,cpy = y;
      next(cpx,cpy);
      
      dfs(G,tatami,cpx,cpy,dc+2);
      eraseTatamiKai(tatami,p3);
      G[ny1][nx1] = 0;
      G[ny2][nx2] = 0;
    }
}

 
int main()
{  
  map<P,int> umekomi;
  umekomi[P(20,20)] = umekomi[P(20,20)] = 2;
  umekomi[P(20,19)] = umekomi[P(19,20)] = 2;
  umekomi[P(20,18)] = umekomi[P(18,20)] = 1;
  umekomi[P(20,17)] = umekomi[P(17,20)] = 0;
  umekomi[P(20,16)] = umekomi[P(16,20)] = 0;
  umekomi[P(20,15)] = umekomi[P(15,20)] = 0;
  umekomi[P(20,14)] = umekomi[P(14,20)] = 0;
  umekomi[P(20,13)] = umekomi[P(13,20)] = 0;
  umekomi[P(20,12)] = umekomi[P(12,20)] = 0;
  umekomi[P(20,11)] = umekomi[P(11,20)] = 2;
  umekomi[P(19,18)] = umekomi[P(18,19)] = 2;
  umekomi[P(19,16)] = umekomi[P(16,19)] = 0;
  umekomi[P(19,14)] = umekomi[P(14,19)] = 0;
  umekomi[P(19,12)] = umekomi[P(12,19)] = 0;
  umekomi[P(18,18)] = umekomi[P(18,18)] = 2;
  umekomi[P(18,17)] = umekomi[P(17,18)] = 2;
  umekomi[P(18,16)] = umekomi[P(16,18)] = 1;
  umekomi[P(18,15)] = umekomi[P(15,18)] = 0;
  umekomi[P(18,14)] = umekomi[P(14,18)] = 0;
  umekomi[P(18,13)] = umekomi[P(13,18)] = 0;
  umekomi[P(18,12)] = umekomi[P(12,18)] = 0;
  umekomi[P(18,11)] = umekomi[P(11,18)] = 0;
  umekomi[P(17,16)] = umekomi[P(16,17)] = 2;
  umekomi[P(17,14)] = umekomi[P(14,17)] = 0;
  umekomi[P(16,16)] = umekomi[P(16,16)] = 2;
  umekomi[P(16,15)] = umekomi[P(15,16)] = 2;
  umekomi[P(16,14)] = umekomi[P(14,16)] = 1;
  umekomi[P(16,13)] = umekomi[P(13,16)] = 0;
  umekomi[P(15,14)] = umekomi[P(14,15)] = 2;
  umekomi[P(15,12)] = umekomi[P(12,15)] = 0;

  while(cin >> H >> W,H|W)
    {
      if((H*W)%2 != 0)
	{
	  cout << 0 << endl;
	  continue;
	}
      //clock_t st,ed;
      //st = clock();
      if(umekomi.find(P(H,W)) != umekomi.end())
	{
	  cout << umekomi[P(H,W)] << endl;
	  continue;
	}
      cnt = 0;
      VVI G(H,VI(W,0));
      VVI tatami(H+(H-2)+1,VI(W,0));
      dfs(G,tatami,0,0,0);
      cout << cnt << endl;
      //cout << "umekomi[P("<<H<<","<<W<<")] = umekomi[P("<<W<<","<<H<<")] = " << cnt  << ";"<< endl;
      //cout << cnt << endl;
      umekomi[P(H,W)] = umekomi[P(W,H)] = cnt;
      //ed = clock();
      //cout << setiosflags(ios::fixed) << setprecision(10) << (double)(ed-st)/CLOCKS_PER_SEC << endl;
    }
  return 0;
}
```