Визначте кількість послідовностей з нулів та одиниць довжини \(N\) (довжина - це загальна кількість нулів та одиниць), в яких ніякі три одиниці не стоять поряд.

Формат вхідних даних

Вводиться натуральне число \(N\), що не перевищує 40.

Формат вихідних даних

Виведіть кількість послідовностей, що шукаються.

Гарантується, що відповідь не перевищує \(2^{31} − 1\).

Приклад вхідних даних

3

Приклад вихідних даних

7