Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714622

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

784. Three ones successively
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

You are given a natural number N. Lets consider sequences with N digits and containing only 0 and 1. It is well known that the number of such sequences equals to 2N. 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 dont 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

Output

1

1

2

2

3

7

 

Tayyorladi: Azat Yusupov
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(60) Barcha urinishlar(118)