Cho số nguyên dương ~n~, hãy tìm số Fibonacci thứ ~n~.

Số Fibonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 1 & \text{nếu $i \leq 2$}\\ f_{i - 1} + f_{i - 2} & \text{nếu $i > 2$} \end{cases} \end{equation} ~

Ví dụ dãy Fibonacci cho ~10~ số đầu tiên: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 75~)

Output

In ra số Fibonacci thứ ~n~.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 40~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

4

Output:

3

Sample Test 2

Input:

10

Output:

55