题目描述

海曙区“呦呦海贝”作品展正在设计一面灯带墙。小禾在设计软件里尝试了一种有趣的拼接方法，依次生成不同版本的灯带图案。

每一盏灯用一个色块表示，各版图案的生成规则如下：

• 第 $1$ 版只有 $1$ 盏青色灯。
• 第 $2$ 版只有 $1$ 盏紫色灯。
• 从第 $3$ 版开始，先复制上一版的完整图案，再复制上上版的完整图案，将两份复制品按这个顺序首尾相接，得到新版图案。连接处的灯不会合并，之前的图案也会保留。

例如，用“青”和“紫”分别表示一盏灯，前五版图案如下：

小禾想先统计图案中的灯的数量，再决定怎样布置展台。给定 $n$，请你计算第 $n$ 版灯带图案一共有多少盏灯。

输入格式

输入一行，包含一个正整数 $n$，表示要查询的版本号。

输出格式

输出一行，包含一个整数，表示第 $n$ 版灯带图案包含的灯的数量。

7

13

1

1

说明/提示

样例 $1$ 中，前七版图案分别有 $1,1,2,3,5,8,13$ 盏灯，所以输出 $13$。

对于 $100\%$ 的数据，$1\le n\le45$。