Задача Язык Мумба-Юмба

Описание

Слова в языке Мумба-Юмба могут состоять только из букв a, b и при этом:

• никогда не содержат двух букв b подряд,
• ни в одном слове никогда не встречается три одинаковых подслова подряд. Например, по этому правилу в язык Мумба-Юмба не могут входить слова aaa (так как три раза подряд содержит подслово a), ababab (так как три раза подряд содержит подслово ab), aabababa (также три раза подряд содержит подслово ab).

Все слова, удовлетворяющие вышеописанным правилам, входят в язык Мумба-Юмба.

Напишите программу, которая подсчитает количество слов длины ровно K символов в языке племени Мумба-Юмба.

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

Вводится одно число K (1 ≤ K ≤ 100 000)

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

Выведите одно число — количество слов в этом языке длины K.