OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1300--满意方案

1300: 满意方案

时间限制: 1 Sec  内存限制: 128 MB
提交: 163  解决: 35
[提交] [状态] [讨论版] [命题人:]

题目描述

农大全能王Jessie Wu喜欢拼接字符,他现在有两种字符分别是A,B,但是他不太喜欢拼接出来的字符中含有AAA、ABA、BAB

他想问问你如果拼接一个长度为n的字符串,有多少种他满意的方案?

输入

第一行输入一个正整数n(1n1e5)

输出

输出方案数对1e9 + 7取模。

样例输入 Copy

3

样例输出 Copy

5

提示

长度为3的时候

5种方案:

BBB

BBA

AAB

BAA

ABB

来源/分类