|
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 polyominoes. Polyomino is usually represented as a set
of sidewise connected squares. Polyomino with n squares is called n-polyomino.
In this problem you are to find a number of distinct free n-polyominoes that fit into rectangle wxh. Free
polyominoes 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 pentominoes (5-polyominoes) that fit into 2x4 rectangle and 3 different
octominoes (8-polyominoes) that fit into 3x3 rectangle.
Input
The input file consists of a single line with 3 integer numbers n, w, and h (1<=n<=10, 1<=w,h<=n).
Output
Write to the output file a single integer number - the number of distinct free n-polyominoes that fit
into rectangle wxh.
Samples
| Input | Output |
|---|
| 5 1 4 | 0 |
| 5 2 4 | 5 |
| 5 3 4 | 11 |
| 5 5 5 | 12 |
| 8 3 3 | 3 |
| 