#include <iostream>
#include <set>
#include <cstdio>

#define REP(i,n) for(int i=0; i<(int)(n); i++)

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

using namespace std;

int t[20][20];
int h, w;

bool ok(int x, int y){
  if(x < 0 || y < 0) return true;
  if(x >= w - 1 || y >= h - 1) return true;
  set<int> s;
  REP(i,2) REP(j,2){
    s.insert(t[y + i][x + j]);
  }
  if(s.count(0)) return true;
  return s.size() != 4;
}

int solve(int pos, int id){
  if(pos == h * w){
    // REP(i,h){ REP(j,w) printf("%2d ", t[i][j]); puts(""); } puts("");
    return 1;
  }
  int x = pos % w;
  int y = pos / w;
  if(t[y][x]) return solve(pos + 1, id);

  int ret = 0;
  if(x != w - 1 && !t[y][x + 1]){
    t[y][x] = t[y][x + 1] = id;
    if(ok(x - 1, y - 1))
      ret += solve(pos + 1, id + 1);
    t[y][x] = t[y][x + 1] = 0;
  }
  if(y != h - 1 && !t[y + 1][x]){
    t[y][x] = t[y + 1][x] = id;
    if(ok(x - 1, y - 1))
      ret += solve(pos + 1, id + 1);
    t[y][x] = t[y + 1][x] = 0;
  }
  return ret;
}

int main(){
  while(true){
    h = getInt();
    w = getInt();

    if(h + w == 0) break;

    printf("%d\n", solve(0, 1));
  }
  return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

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 <set>
#include <cstdio>

#define REP(i,n) for(int i=0; i<(int)(n); i++)

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

using namespace std;

int t[20][20];
int h, w;

bool ok(int x, int y){
  if(x < 0 || y < 0) return true;
  if(x >= w - 1 || y >= h - 1) return true;
  set<int> s;
  REP(i,2) REP(j,2){
    s.insert(t[y + i][x + j]);
  }
  if(s.count(0)) return true;
  return s.size() != 4;
}

int solve(int pos, int id){
  if(pos == h * w){
    // REP(i,h){ REP(j,w) printf("%2d ", t[i][j]); puts(""); } puts("");
    return 1;
  }
  int x = pos % w;
  int y = pos / w;
  if(t[y][x]) return solve(pos + 1, id);

  int ret = 0;
  if(x != w - 1 && !t[y][x + 1]){
    t[y][x] = t[y][x + 1] = id;
    if(ok(x - 1, y - 1))
      ret += solve(pos + 1, id + 1);
    t[y][x] = t[y][x + 1] = 0;
  }
  if(y != h - 1 && !t[y + 1][x]){
    t[y][x] = t[y + 1][x] = id;
    if(ok(x - 1, y - 1))
      ret += solve(pos + 1, id + 1);
    t[y][x] = t[y + 1][x] = 0;
  }
  return ret;
}

int main(){
  while(true){
    h = getInt();
    w = getInt();

    if(h + w == 0) break;

    printf("%d\n", solve(0, 1));
  }
  return 0;
}
```