五一休闲(一)
题目描述
今天是五一劳动节的放假期间,小算却始终没有闲着,他一直都在刷算法题,可能是他认为老师出的题太简单了,没有意思 ~,于是他自己给自己出了了个 问题:
一条手链,可以穿两种颜色的珠子进去,分别是 灰色和白色。可是呢,小算个人不太喜欢灰色,可能是因为它的颜色不是太突出(他希望让灰色来衬拖白色)。为了让白色使得手链更加显眼,每两颗白色珠子之间必定不能相邻,这样使得白色珠子更加的分散,而灰色珠子是可以相邻的,现在他不想考虑太多,手链的首尾由于还需要用铁质加工( 假设不算相邻 ),一串手链上尽量保证符合以上条件即可,无论穿多少颗白色珠子。
现在假设有灰白色珠子无数颗,请问长度为 N 的手链(能穿 N 颗珠子)有多少种穿接方法(保证穿满)。
输入格式
输入包含一行,第一行包含 1 个整数 n ,表示手链的长度。
输出格式
输出一个整数代表穿接方法的种数。
数据范围
1 ≤ n ≤ 30
样例
样例输入
2
样例输出
3
样例输入
23
样例输出
75025
时限: 1s
出题人: dreamy-xay