Внутривузовские олимпиады/1-6 курсы/ТУСУР 2016


10. Диета

Автор задачи: Соловьёв Виктор
Источник: Первый внутривузовский тур Региональной студенческой предметной олимпиады по программированию 13 марта 2016
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Алексей решил привести себя в форму к лету. Он не только занялся спортом, но и сел на творожную диету. Информацию о поедании творога в течение диеты он вносит в специальный дневник.

Каждое утро Алексей выходит на пробежку, покупает творог и завтракает им, в обед он так же ест творог. В первое утро Алексей покупает две пачки творога, во все последующие - по одной. За раз он съедает половину пачки, вторую половину он может доесть позже. При этом съедая первую половину пачки, Алексей вписывает в дневник w, доедая вторую - h. Срок годности творога - трое суток, то есть утром четвёртого дня Алексей уже не может есть творог, купленный утром первого дня. Каково количество различных последовательностей, которые могли бы получиться в дневнике Алексея к вечеру N-го дня?

Входные данные

Единственная строка входных данных содержит одно натуральное число N - количество дней, в течении которых Алексей придерживался своей диеты (1 ≤ N ≤ 30).

Выходные данные

Вывести одно целое число - ответ на вопрос задачи.

Примеры
Стандартный вводСтандартный вывод
12
25
Пояснения к примерам

Возможные последовательности во втором примере: wwwh, wwhw, wwhh, whww, whwh