符文排列

题目描述

在一座远古神庙的石门上，刻着 $n$ 个凹槽。祭司们需要将“火之符文”（用 0 表示）和“冰之符文”（用 1 表示）嵌入这些凹槽中。

为了维持神庙能量的稳定，符文的排列必须遵循一个严格的准则：不能有超过两个相同的符文连续排列。也就是说，排列中不能出现 "000" 或者 "111"。

请你计算，一共有多少种不同的排列方案能够保持石门的能量稳定？由于结果可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

输入格式

输入一个整数 $n$，表示凹槽的数量。

输出格式

输出一个整数，表示合法的排列方案数对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

3

输出 #1

6

输入输出样例 #2

输入 #2

5

输出 #2

14

数据范围

对于 $60\%$ 的数据，$1 \le n \le 1000$。

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