DSCS 2013 Triangular and hexagonal grid. Part 2
Башни
Башня состоит из основания и, возможно, надстройки. В основании башни размещены несколько равных равносторонних треугольников, основания которых находятся на горизонтальной прямой (см. рисунок ниже).
Далее конструируем надстройку из треугольников, равных треугольникам, составляющим основание. При этом разрешено выполнять два действия.
1. "Утопить" треугольник между двумя соседними треугольниками (см.рис.)
2. Если треугольник "утоплен" так, как показано в предыдущем пункте, то разрешается присоединить сверху к нему еще один треугольник (см.рис.)
Необходимо по известному количеству треугольников в основании башни найти количество возможных башен.
Input data
Вводится количество треугольников в основании башни N (N ≤ 100).
Output data
Вывести количество возможных башен.
На рисунке изображены все возможные башни для примера из условия.
Examples
3
11