Башни
Башня состоит из основания и, возможно, надстройки. В основании башни размещены несколько равных равносторонних треугольников, основания которых находятся на горизонтальной прямой (см. рисунок ниже).
Далее конструируем надстройку из треугольников, равных треугольникам, составляющим основание. При этом разрешено выполнять два действия.
1. "Утопить" треугольник между двумя соседними треугольниками (см.рис.)
2. Если треугольник "утоплен" так, как показано в предыдущем пункте, то разрешается присоединить сверху к нему еще один треугольник (см.рис.)
Необходимо по известному количеству треугольников в основании башни найти количество возможных башен.
Входные данные
Вводится количество треугольников в основании башни N (N ≤ 100).
Выходные данные
Вывести количество возможных башен.
На рисунке изображены все возможные башни для примера из условия.
