Ở một hàm đệ qui, ta cần có 2 thứ: lời gọi hàm và điều kiện dừng.

Sau đây, Bob cho bạn một bài toán và Bob yêu cầu bạn hãy giải quyết nó bằng Đệ qui.

Cho 1 số nguyên n (Với 1≤n≤25). Bạn hãy lập trình đệ qui để tính số Fibonacci thứ n.

Biết số Fibonacci - https://vi.wikipedia.org/wiki/Dãy_Fibonacci - là số mà số sau bằng tổng 2 số trước. Bắt đầu với số thứ 1 là 1 và số thứ 2 cũng là 1.

Input

Dòng đầu tiên có chứa 1 số nguyên n (Với 1≤n≤25).

Output

Một dòng duy nhất là 1 số là số Fibonacci thứ n.

Examples

Input

1

Output

1

Input

2

Output

1

Input

3

Output

2

Input

4

Output

3