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

题目描述

拓拓和思思正在玩扔硬币的游戏，拓拓负责扔，思思负责记录每次扔完的结果，用 $0$ 表示正面，$1$ 表示反面。

拓拓扔了太多次硬币，已经不记得自己每次扔的是什么结果，他只记得自己一共扔了 $n$ 次。

拓拓希望自己扔出的结果序列中 没有连续三次或以上的正面或反面，但他不知道自己扔出的 $01$ 序列是什么，所以无从得知。

你能帮拓拓算一下，有多少种可能的 $01$ 序列满足他的要求吗？

答案可能很大，输出答案请对 $10^9+7$ 取模。

输入格式

输入一个整数 $n$，表示拓拓扔硬币的次数。

输入格式

输出一个整数：表示答案模 $10^9+7$ 的余数。

样例

3

6

解释#1

有六种方案：001，010，011，110，101，100。

10

178

数据范围

• 对于 $100\%$ 的数据，$1\leq n\leq 10^6$。