题目描述

斐波那契数列 F₁,F₂,…,Fₖ,… 如下定义：

F₁=F₂=1

Fₖ=Fₖ₋₁+Fₖ₋₂,(k≥3)

给出正整数n，计算Fₙ的值

输入格式

一行，1 个正整数n

输出格式

一行，输出Fₙ的值

输入样例 #1

99

输出样例 #1

218922995834555169026

输入样例 #2

14

输出样例 #2

377

输入样例 #3

10

输出样例 #3

55

数据范围与约定

1≤n≤4000

F₄₀₀₀的值不超过1000位