Problem1447--卡姆喜欢的字符串

1447: 卡姆喜欢的字符串

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

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

Input 

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

Output 

输出一个整数表示答案。

Sample Input Copy 

3

Sample Output Copy 

5

HINT

SQS  ,   SQQ  ,   QQQ  , QQS ,  QSQ.

Source/Category

admin 
Submit