Số Fibonacci được xác định bởi công thức sau:

f[1] = 1.

f[2] = 1.

f[n] = f[n-1] + f[n-2].

Bài toán đặt ra tìm số Fibonacci thứ n (1<=n<=1000)

Input

Một dòng duy nhất chứa số nguyên dương n (1<=n<=1000).

Output

Một số nguyên dương duy nhất có số chữ số không vượt quá 1000 chữ số

Test 1:

Input:

5

Output:

5

Test 2:

Input:

1000

Output:

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875