Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2669
Lattice Animals

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyminoes. Polymino is usually represented as a set of sidewise connected squares. Polymino with n squares is called n-polymino.

In this problem you are to find a number of distinct free n-polyminoes that fit into rectangle w * h. Free polyminoes can be rotated and flipped over, so that their rotations and mirror images are considered to be the same.

For example, there are 5 different pentaminoes (5-polyminoes) that fit into 2 * 4 rectangle and 3 different octominoes (8-polyminoes) that fit into 3 * 3 rectangle.

Input

There are several test cases in the input. Each case consists of a single line with 3 integer numbers n, w, and h (n ≤ 10, 1 ≤ w, h ≤ n).

Output

Write to the output file a single integer number --- the number of distinct free n-polyminoes that fit into rectangle w * h.

Sample Input

5 1 4
5 2 4
5 3 4
5 5 5
8 3 3

Sample Output

0
5
11
12
3

Source: Northeastern Europe 2004
Submit    Status