Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3363
Another Brick in the Wall

Time Limit: 2 Seconds      Memory Limit: 32768 KB

The company Wall Construction Inc (WC Inc) is preparing its new software project. The goal of this project is to automatically plan garden walls. You, the company's leading developer, are asked to quickly write the prototype of the system.

The wall is constructed of several bricks. Bricks are organized in layers, the bottom layer contains m bricks lying next to each other. The total number of layers is n. The bricks in each next layer are shifed by one half of the brick horizontaly compared to the bricks of the previous layer.

The number of bricks in different levels may be different, however the wall must be stable. The wall is considered stable if all of its bricks are stable. The brick is stable if one of the following conditions is satisfied:

  1. the brick belongs to the first level;
  2. the brick is lying on two bricks (none of the two bricks directly under it is missing);
  3. the brick is lying on one brick and:
    • there is a brick directly upon it on the side that is lying on a brick;
    • there is no brick directly upon it on the side that is not lying on a brick;
  4. the brick is lying on one brick and there is a brick in the same layer, directly next to it at the side that is not lying on a brick.

The pictures below show possible cases of stable bricks.

Note, that only bricks that affect the stability of the shaded brick are shown. Since all these bricks must also be stable, actually some other bricks must also exist for the whole wall to be stable.

Your first task is, given m and n find the number of stable walls.


The input file contains m and n (1 ≤ m, n ≤ 8).

There are multiple test cases. Process to the end of file.


Output the number of stable walls with m bricks in the first layer and n layers.

Sample Input

3 3

Sample Output



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