问题1447--卡姆喜欢的字符串

1447: 卡姆喜欢的字符串

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交
解决: 40提交量: 62统计

题目描述

卡姆非常喜欢小石学长的名字，我们知道小石学长的名字里只有“S”和“Q”,以至于卡姆英文字母只喜欢“S”和“Q”。
因此卡姆喜欢只含有“S”和“Q”的字符串，且字符串中不能出现两个连续的“S”。
请你求出有多少种长度为n的字符串是卡姆喜欢的字符串。答案对1e9+7取模（取余）。
（1e9就是10的9次方）

输入 

输入一个整数n。
1<=n<=100000

输出 

输出一个整数表示答案。

样例输入 Copy 

3

样例输出 Copy 

5

提示

SQS  ,   SQQ  ,   QQQ  , QQS ,  QSQ.

来源/分类

201801014611 
提交