Задача H. Забавная игра ≡

Условие

Классики — старинная детская игра, популярная во всём мире. Одной из разновидностей правил являются следующие: на асфальт наносятся прямоугольники, как на рисунке ниже. Каждый участник совершает прыжки: сначала одной ногой на любое из двух полей по своему выбору, то есть на 1 или на 2, потом обеими ногами на поле с номером 3. Затем опять одной ногой на любое из двух полей по своему выбору, то есть на 4 или на 5, потом обеими ногами на поле с номером 6 и так далее. Остановиться можно в любой момент, а задача — набрать в сумме полей, на которые пришлись прыжки, ровно n.

Для указанного n определите количество различных подходящих маршрутов.

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 10000

Пояснения к примерам

Сумму 22 в первом примере можно набрать тремя способами:

1. 1 + 3 + 4 + 6 + 8;
2. 1 + 3 + 5 + 6 + 7;
3. 2 + 3 + 4 + 6 + 7.

Сумму 3 во втором примере набрать не получится: после первого прыжка можно набрать только 1 или 2, а после второго — только 4 или 5.

Примеры тестов

22

3

3

0