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