题目描述

观察这个数列：$1、1、2、3、5、8、13、21、34……$

从第三项开始，数列的每个数字都是前面两个数字的和。例如，$2=1+1$。

输入一个整数 $n(0\le n\le 48)$，输出第 $n$ 项数组元素。

特别的，第 $0$ 项是 $0$ 。

建议定义数组时用全局变量。局部变量无法定义很大的数组。

输入格式

一行一个自然数 $n$。

输出格式

只有 $1$ 行一个整数，表示第 $n$ 项数组元素。

样例

6

8

1

1

提示

对于所有数据：$0\le n\le 48$