题目描述

有一个 $1 \times n$ 的长方形，用 $1 \times 1$ 和 $1 \times 2$ 的骨牌铺满方格，请问有多少种铺法？

例如当 $n=3$ 时，为 $1 \times 3$ 的方格。此时用 $1 \times 1$ 和 $1 \times 2$ 的骨牌铺满方格，共有三种铺法。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示铺设方案总数。

样例

5

8

数据范围

• $1 \le n \le 50$
• 答案不超过 $64$ 位整数范围。