За цим натуральним \(n\) визначте кількість послідовностей довжини \(n\) з 0 і 1, що не містять трьох однакових символів поспіль.

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

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

Вводиться натуральне число.

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

Виведіть відповідь на завдання.

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

3

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

6