Huấn luyện viên Quýt nghĩ ra bài tập chuyền bóng theo dãy số nổi tiếng nhất lịch sử toán học: phút thứ nhất cả đội chuyền 1 đường, phút thứ hai chuyền 1 đường, và từ phút thứ ba trở đi, số đường chuyền của mỗi phút bằng tổng số đường chuyền của hai phút liền trước: 1, 1, 2, 3, 5, 8, 13, 21, ...

Cho số nguyên dương n, hãy in ra số đường chuyền ở phút thứ n, biết ~F(1) = 1~, ~F(2) = 1~ và ~F(n) = F(n-1) + F(n-2)~ với ~n ≥ 3~.

Input: Một số nguyên dương n.

Output: Giá trị của ~F(n)~.

Ràng buộc: ~1 ≤ n ≤ 90~. Gợi ý: ~F(90)~ là số rất lớn, vượt xa phạm vi kiểu int.

Ví dụ 1:

Input:

6

Output:

8

Ví dụ 2:

Input:

1

Output:

1