Задача Unizero. Першокласнику Матвію серед усіх цифр найбільше подобаються одиниця та нуль. Він намагається визначити кількість різних послідовностей цифр довжиною n з такими властивостями: між будь-якою парою сусідніх одиниць у кожній послідовності повинна знаходитися одна й та ж кількість нулів (не менше від одного). Послідовність може починатися і з нуля, і з одиниці. Допоможіть Матвію.

Технічні умови. Програма Unizero читає з пристрою стандартного введення єдине натуральне число n (3<=n<=5000000). Програма виводить на пристрій стандартного виведення шукану величину – кількість можливих послідовностей.

Приклад

Введення 4

Виведення 3

КОМЕНТАР ДО ПРИКЛАДУ. Послідовності, які задовольняють умові задачі при n=4: 1010 0101 1001.