Dãy Fibonacci được định nghĩa như sau: ~F_1 = 1~, ~F_2 = 1~ và ~F_k = F_{k-1} + F_{k-2}~ với ~k \ge 3~. Vài số hạng đầu là ~1, 1, 2, 3, 5, 8, 13, \dots~ Cho ~n~, hãy tìm ~F_n~.

Dữ liệu vào

Một số nguyên dương ~n~ (~1 \le n \le 90~).

Kết quả

In ra giá trị của ~F_n~.

Ví dụ

Ví dụ 1

Input:

7

Output:

13

Ví dụ 2

Input:

10

Output:

55

Giải thích

Dãy bắt đầu 1 1 2 3 5 8 13, nên ~F_7 = 13~. ~F_{90}~ xấp xỉ ~2.9 \times 10^{18}~ nên cần long long.