题目描述

扔一枚硬币有两种结果：正面与反面。给定 $n$，请统计有多少种扔硬币的结果中不含三个连续的正面硬币且不含三个连续的反面硬币。

由于答案可能很大，请对 $10^9+7$ 取余。

输入格式

一个数 $n$。

输出格式

输出一个整数代表答案。

3

6

数据规模与约定

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