题目描述

第1个月只有一对新生兔子，第2个月仍为一对；每对兔子从第3个月开始，每月繁殖一对新兔子，新生兔子也遵守同样的规则。兔子不会死亡。求第 $n$ 个月的兔子总对数。

输入格式

输入一个整数 $n$。

输出格式

输出兔子总对数。

样例

6

8

数据范围

$1\le n\le46$。