首页 > 试题广场 >

超越学姐爱字符串

[编程题]超越学姐爱字符串
超越学姐非常喜欢自己的名字,以至于英文字母她只喜欢“c”和“y”。因此超越学姐喜欢只含有“c”和“y”的字符串,且字符串中不能出现两个连续的“c”。请你求出有多少种长度为n的字符串是超越学姐喜欢的字符串。答案对1e9+7取模。

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


输出描述:
输出一个整数表示答案。
示例1

输入

3

输出

5

说明

cyy,cyc,yyy,yyc,ycy