Cho 1 số nguyên n (Với 1≤n≤25). 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