Lattice Animals

Time limit2sMemory limit128 MB

Summary

Count free n-polyominoes (up to rotation and reflection) that fit inside a w by h rectangle, with n up to 10.

Level: Medium7 of 10
Topics: Backtracking, Brute force, Geometry, Hash map
Solved: No attempts yet

Problem

A lattice animal is a set of connected cells on a lattice. Lattice animals on a square lattice are an especially popular subject of study and are also known as polyominoes. A polyomino is usually represented as a set of edge-connected unit squares. A polyomino with $n$ squares is called an $n$ -polyomino.

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

For example, there are 5 different pentominoes (5-polyominoes) that fit into a $2 \times 4$ rectangle, and 3 different octominoes (8-polyominoes) that fit into a $3 \times 3$ rectangle.

Input

The input consists of a single line with three integers $n$ , $w$ , and $h$ ( $1 \le n \le 10$ , $1 \le w, h \le n$ ).

Output

Output a single integer — the number of distinct free $n$ -polyominoes that fit into a $w \times h$ rectangle.

Examples5

Example 1
Input
```
5 1 4
```
Expected output
```
0
```
Example 2
Input
```
5 2 4
```
Expected output
```
5
```
Example 3
Input
```
5 3 4
```
Expected output
```
11
```
Example 4
Input
```
5 5 5
```
Expected output
```
12
```
Example 5
Input
```
8 3 3
```
Expected output
```
3
```