该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

今天是五一劳动节的放假期间，小算却始终没有闲着，他一直都在刷算法题，可能是他认为老师出的题太简单了，没有意思 ~，于是他自己给自己出了了个 问题：

一条手链，可以穿两种颜色的珠子进去，分别是 灰色和白色。可是呢，小算个人不太喜欢灰色，可能是因为它的颜色不是太突出（他希望让灰色来衬拖白色）。为了让白色使得手链更加显眼，每两颗白色珠子之间必定不能相邻，这样使得白色珠子更加的分散，而灰色珠子是可以相邻的，现在他不想考虑太多，手链的首尾由于还需要用铁质加工（ 假设不算相邻 ），一串手链上尽量保证符合以上条件即可，无论穿多少颗白色珠子。

现在假设有灰白色珠子无数颗，请问长度为 N 的手链（能穿 N 颗珠子）有多少种穿接方法（保证穿满）。

输入格式

输入包含一行，第一行包含 1 个整数 n ，表示手链的长度。

输出格式

输出一个整数代表穿接方法的种数。

数据范围

1 ≤ n ≤ 30

样例

样例输入

2

样例输出

3

样例输入

23

样例输出

75025

时限： 1s
出题人： dreamy-xay