Вежі#4630
Вежа складається з підстави та, можливо, надбудови. Підстава сформована з кількох однакових рівносторонніх трикутників, усі розташовані своїми основами на одній горизонтальній лінії (див. ілюстрацію нижче).
Для побудови надбудови ми використовуємо трикутники, ідентичні тим, що в основі. Під час цього процесу дозволяється виконувати дві дії:
1. Вбудувати трикутник між двома сусідніми трикутниками (див. ілюстрацію).
2. Після того, як трикутник вбудовано описаним вище чином, можна поставити ще один трикутник поверх нього (див. ілюстрацію).
Знаючи кількість трикутників у підставі вежі, визначте загальну кількість можливих конфігурацій вежі.
Вам дано кількість трикутників у підставі вежі (N \leq 100).
Виведіть загальну кількість можливих конфігурацій вежі.
На ілюстрації показано всі можливі вежі для прикладу, наведеного в умові.
Приклад 1