You are given a natural number

You are given a natural number N. Let’s consider sequences with N digits and containing only 0 and 1. It is well known that the number of such sequences equals to 2^N. For example for N=3 such sequences: 000, 001, 010, 011, 100, 101, 110, 111.

Your task is to calculate then number of sequences not containing three ones successively. Among given sequences 111 don’t satisfy to such requirement.

Input__The_input_contains_single_integer_number_N_(1_≤_N_≤_70).__Output__Output_one_number_–_the_answer_to_the_problem._Samples'>Input

The input contains single integer number N (1 ≤ N ≤ 70).

Output

Output one number – the answer to the problem.
Samples

№	Input	Output
1	1	2
2	3	7

Sizga N natural raqami berilgan, keling, N raqamli va faqat 0 va 1 raqamlarni o'z ichiga olgan ketma-ketliklarni ko'rib chiqamiz. Masalan, N = 3 uchun bunday ketma-ketliklar: 000, 001, 010, 011, 100, 101, 110, 111.

Sizning vazifangiz ketma-ket uchta ketma-ketlikni o'z ichiga olmagan ketma-ketliklar sonini hisoblashdir. Ushbu ketma-ketliklar orasida 111 bu talabni qondirmaydi.

Kiritish

Kiritilgan N (1 ≤ N-70) bitta butun sonni o'z ichiga oladi.

Chiqish

Bitta raqamni chiqaring - muammoga javob.