###### Category

###### Similar Problems

## 0784. Three ones successively

###### Time limit : 1000 ms

Memory limit : 64 mb

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 |
Output |

1 |
1 |
2 |

2 |
3 |
7 |