题目描述

训练营植物角里有一种“回声小树”。

高度为 1 的小树有 1 片叶子。

高度为 2 的小树有 2 片叶子。

当这种小树继续长高时，它的树冠会分成两部分：

• 一部分长成比它矮 1 的小树形态；
• 另一部分长成比它矮 2 的小树形态。

整棵树的叶子数，就是这两部分叶子数的总和。

给定小树高度 n，请你计算它一共有多少片叶子。

输入格式

输入一个整数 n，表示小树高度。

输出格式

输出一行，一个整数，表示高度为 n 的小树叶子数。

样例

5

8

样例说明

高度 1 到 5 的叶子数依次为：

1, 2, 3, 5, 8

数据范围

• 1 <= n <= 35