Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2563
Long Dominoes

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Find the number of ways to tile an m*n rectangle with long dominoes -- 3*1 rectangles.

Each domino must be completely within the rectangle, dominoes must not overlap (of course, they may touch each other), each point of the rectangle must be covered.


Input

The input contains several cases. Each case stands two integers m and n (1 <= m <= 9, 1 <= n <= 30) in a single line. The input ends up with a case of m = n = 0.


Output

Output the number of ways to tile an m*n rectangle with long dominoes.


Sample Input

3 3
3 10
0 0

Sample Output

2
28


Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status