题目描述

数列的第一项和第二项均为 $1$，此后每项等于前两项之和。求第 $k$ 项。

输入格式

一行一个正整数 $k$。

输出格式

输出第 $k$ 项。

样例

19

4181

数据范围

$1\le k\le46$。