ENG  RUS Timus Online Judge Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1531. Zones on a Plane

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ Consider zones zi on a plane which consist of triangles. Zone z1 consists of two right-angled isosceles triangles, forming a square. Zone zn + 1 is produced from zone zn in the following way. For each triangle from the previous zone, construct two isosceles right-angled triangles on each of its two legs as a hypotenuse. Then, remove every triangle that is a part of a zone with lower number. The remaining triangles constitute the zone zn + 1.
Given an integer number n, find how many simple polygons constitute the zone zn.

### Исходные данные

There is a single integer n (1 ≤ n ≤ 2000) on the first line of the input.

### Результат

Output a single number — the number of simple polygons zone zn consists of.

### Примеры

исходные данныерезультат
`1`
`1`
`2`
`4`
`3`
`8`
`4`
`12`
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
Метки: нет