0474 - Fibonacci number

時間制限 1 秒 / メモリ制限 64 MB / 得点 3 / Writer root / x 49 / 統計 /


TLE
1sec
MLE
64MB
得点
3

問題

Fibonacci sequence of numbers

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2

In a defined sequence.

Make a program that outputs the n-th Fibonacci sequence.

Input

N

Given the number N of the Fibonacci sequence to be determined in the first line.

Output

You should output the N-th of the Fibonacci sequence.

Constraint

Satisfies the following for all of the input and output case.

  • 1 <= N <= 90

Input and output example

Input example Ⅰ

6

Output example Ⅰ

8

Input example Ⅱ

1

Output example Ⅱ

1

Input example Ⅲ

25

Output example Ⅲ

75025