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} ~

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