题目背景

洛阳桥是中国古代著名的跨海梁式大石桥。修筑时采用了创新的“筏形基础”，上面铺设了整齐的石梁。

题目描述

工程队现要在一排长为 $N$、宽为 1 且分为 $N$ 个网格的桥面上铺设石板。可供选择的石板有三种：

• 花岗岩板（G）
• 辉绿岩板（D）
• 砂岩板（S）

每一个网格必须且只能铺设一块石板。然而，由于不同石料的抗浪涌撞击性能不同，铺设必须满足以下技术规范：

1. 不能连续两个网格都铺设砂岩板（S）。
2. 花岗岩板（G） 的后面不能紧跟辉绿岩板（D）（即不能出现 GD 组合）。

请问，要铺满长度为 $N$ 的桥面，共有多少种合法的铺设方案？由于方案数可能很大，请输出结果对 $10^9+7$ 取模的值。

输入格式

输入仅包含一个正整数 $N$，表示桥面的网格长度。

输出格式

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

输入输出样例

输入 #1

2

输出 #1

7

样例说明： 长度为 2 时，所有可能的 9 种排列中，非法的有 SS（违反规则1）和 GD（违反规则2），其余 7 种（GG, GS, DG, DD, DS, SG, SD）均合法。

说明/提示

对于 $100\%$ 的数据：$1 \le N \le 10^5$。