# 斐波那契数

题目描述

斐波那契数列定义为 F1=1，F2=1，Fn=F(n-1)+F(n-2)。输入 n，输出 Fn。

输入格式

一行一个正整数 n。

输出格式

输出一个整数，表示 Fn。

样例

样例输入 1

6

样例输出 1

8

数据范围

$1 \le n \le 45$