#H. xzl喜欢yy

远端评测题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

xzl非常喜欢yy，以至于英文字母他只喜欢“x”和“y”。因此xzl喜欢只含有“x”和“y”的字符串，
且字符串中不能出现两个连续的“x”。
请你求出有多少种长度为n的字符串是xzl喜欢的字符串。答案对1e9+7取模。

Input

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

输出一个整数表示答案。

xyy,xyx,yyy,yyx,yxy