Towers

The tower is composed of a base and, potentially, a superstructure. The base consists of several identical equilateral triangles, all aligned with their bases on a horizontal line (refer to the illustration below).

To build the superstructure, we use triangles identical to those in the base. During this process, two actions are permissible:

1. Embed a triangle between two adjacent triangles (see illustration).

2. Once a triangle is embedded as described above, you may place another triangle on top of it (see illustration).

Given the number of triangles in the base of the tower, determine the total number of possible tower configurations.

Output

Output the total number of possible tower configurations.

The illustration shows all possible towers for the example provided in the problem statement.