不会连亮的灯带

题目描述

有 n 个按顺序排列的灯，每个可以亮或不亮，要求任意两个相邻灯不能同时亮。求不同亮灭方案数。n=0 时有一种空方案。

输入格式

输入 n。

输出格式

输出方案数。

样例 1

输入

3

输出

5

说明

按 0 灭、1 亮写为 000、001、010、100、101。

样例 2

输入

0

输出

1

说明

空方案也计入。

数据范围

• 0≤n≤40；答案使用 long long。