Tatami

면접 대비

시간 제한8초메모리 제한512 MB

요약

H×W 격자를 1×2 다다미로 빈틈없이 덮되, 한 내부 점에서 네 다다미의 모서리가 만나지 않도록 하는 경우의 수를 센다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

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.

입력

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.

출력

For each dataset, print the number of possible ways to spread tatami mats in one line.

예제1

예제 1
입력
```
3 4
4 4
0 0
```
예상 출력
```
4
2
```