时间限制:1000ms  空间限制:256MB

题目描述

小高斯热爱劳动，经常帮父亲整理家里的小花园，其中有一个2 * n的长方形砖墙面，需要使用一种1 * 2的长方形大瓷砖去贴墙。附近的一个老爷爷就走来问高斯：“像你家这样一面墙，能有多少种贴这种瓷砖的方法呢？”高斯想一想，很快就回答出来！事情传开后，大家都夸奖小高斯！

例如n=3时，为2 * 3方格，此时用1 * 2瓷砖铺满方格，共有3种铺法

输入格式

一行一个整数n<=30

输出格式

一行一个整数 铺法

样例

输入#1

3

输出#1

3