题目描述

小蓝有两双不同的鞋，可以换着穿，一双鞋，可以穿1天就换另一双，也可以连续穿2天再换另一双，但同一双鞋不能连续穿3天。用这两双鞋搭配穿n天，总共有多少种不同的方案。两种方案，只要有一天穿的鞋子不一样，就认为是不同的方案。用A、B代表这两双不同的鞋。当n=4时，有以下穿鞋的方案。本题要求采用递推实现。

AABB、ABAB、ABBA、AABA、ABAA
BBAA、BABA、BAAB、BBAB、BABB

输入格式

输入数据占一行，为一个正整数n，代表天数n，n≤90。

输出格式

输出数据占一行，为求得的答案。

输入输出样例 #1

输入 #1

4

输出 #1

10

输入输出样例 #2

输入 #2

90

输出 #2

9320093220751060618

说明/提示

本题出处

本题源自以下教材的编程习题：王桂平, 周思益, 周迎川著. C++编程与信息学竞赛数学基础, 北京大学出版社, 2025年7月出版.