Problem K. Треугольная пицца
Input file name: triangular.in
Output file name: triangular.out
Time limit: 2 s
Memory limit: 256 MB

Пиццерия «Pizza C:/Temp’o» освоила выпуск нового типа пиццы с кусочками треугольной формы. Пицца состоит из нескольких одинаковых равносторонних треугольников. Более того, фигура является связной (два треугольника непосредственно соседствуют, если они имеют общую сторону), но может содержать «дырки».

Сколько всего существует различных форм для пиццы из N кусков? Две фигуры считаются одинаковыми, если их можно совместить наложением (фигуры можно двигать и вращать в плоскости, но нельзя переворачивать).

Input

На входе записано одно целое число N (1 ≤ N ≤ 16).

Output

Выведите одно число — количество возможных форм пиццы.

Examples

triangular.in triangular.out
2
1
4
4