Số Fibonacci thứ n

Dãy Fibonacci được định nghĩa bởi \(F_0 = 0\), \(F_1 = 1\) và \(F_k = F_{k-1} + F_{k-2}\) với mọi \(k \ge 2\) (các số đầu tiên là \(0, 1, 1, 2, 3, 5, 8, \dots\)).

Cho số nguyên \(n\), hãy tính \(F_n\). Đây là bài luyện đệ quy, nhưng bạn có thể giải bằng cách nào tuỳ ý miễn đúng và đủ nhanh.

Input

• Một số nguyên \(n\).

Output

• In ra \(F_n\).

Constraints

• \(0 \le n \le 40\).

Sample Input 1

4

Sample Output 1

3

Sample Input 2

5

Sample Output 2

5

Sample Input 3

10

Sample Output 3

55

Sample Input 4

40

Sample Output 4

102334155