Pinary Numbers

Interview

Time limit2sMemory limit128 MB

Summary

Count binary strings of length N that start with 1 and have no two consecutive 1s, using Fibonacci-style counting with big integers up to N=90.

Level: Easy3 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

A binary number is a number made only of 0s and 1s. A pinary number is a binary number that satisfies both of the following conditions.

It does not start with 0.
It never has two consecutive 1s. In other words, it does not contain the substring 11.

Numbers such as 1, 10, 100, 101, 1000, and 1001 are pinary numbers. On the other hand, 0010101 is not a pinary number because it starts with 0, and 101101 is not a pinary number because it contains 11.

Given an integer N, find the number of pinary numbers of length N. The value of N satisfies 1 <= N <= 90.

Input

The first line contains the integer N.

Output

Print the number of pinary numbers of length N on the first line.

Examples1

Example 1
Input
```
3
```
Expected output
```
2
```