#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int w, h;
bool exist[30][30];

int calc(int x, int y, int low, int high) {
  //cout << x << " " << y << " "<< low << " " << high << endl;
  if (y == h) { return 1; }
  if (x == w + 1) { return 0; }
  if (x == w) {
    int nhigh = high & ~(1 << x);
    return calc(0, y + 1, nhigh, 0);
  }
  if (exist[y][x]) {
    int nhigh = high | (1 << x) | (1 << (x + 1));
    return calc(x + 1, y, low, nhigh);
  }
  int ret = 0;
  int prev = (low >> (x + 1)) & 1;
  int next = (low >> (x + 2)) & 1;
  exist[y][x] = true;
  if (!exist[y][x + 1] && !next) {
    int nhigh = high | (1 << (x + 2));
    exist[y][x + 1] = true;
    ret += calc(x + 2, y, low, nhigh);
    exist[y][x + 1] = false;
  }
  if (!prev && y != h - 1) {
    int nhigh = high & ~(1 << x);
    exist[y + 1][x] = true;
    ret += calc(x + 1, y, low, nhigh);
    exist[y + 1][x] = false;
  }
  exist[y][x] = false;
  return ret;
}

int main() {
  MEMSET(exist, false);
  while (scanf("%d %d", &w, &h), w|h) {
    if (w > h) { swap(w, h); }
    printf("%d\n", calc(0, 0, 0, 0));
  }
}
### Prompt

Please create a solution in cpp 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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int w, h;
bool exist[30][30];

int calc(int x, int y, int low, int high) {
  //cout << x << " " << y << " "<< low << " " << high << endl;
  if (y == h) { return 1; }
  if (x == w + 1) { return 0; }
  if (x == w) {
    int nhigh = high & ~(1 << x);
    return calc(0, y + 1, nhigh, 0);
  }
  if (exist[y][x]) {
    int nhigh = high | (1 << x) | (1 << (x + 1));
    return calc(x + 1, y, low, nhigh);
  }
  int ret = 0;
  int prev = (low >> (x + 1)) & 1;
  int next = (low >> (x + 2)) & 1;
  exist[y][x] = true;
  if (!exist[y][x + 1] && !next) {
    int nhigh = high | (1 << (x + 2));
    exist[y][x + 1] = true;
    ret += calc(x + 2, y, low, nhigh);
    exist[y][x + 1] = false;
  }
  if (!prev && y != h - 1) {
    int nhigh = high & ~(1 << x);
    exist[y + 1][x] = true;
    ret += calc(x + 1, y, low, nhigh);
    exist[y + 1][x] = false;
  }
  exist[y][x] = false;
  return ret;
}

int main() {
  MEMSET(exist, false);
  while (scanf("%d %d", &w, &h), w|h) {
    if (w > h) { swap(w, h); }
    printf("%d\n", calc(0, 0, 0, 0));
  }
}
```