You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

双龙桥的元宵灯会

题目背景

在云南建水的城西，横跨于泸江河上的双龙桥（俗称十七孔桥）是著名的古桥梁建筑。每逢元宵佳节，临安古城的居民们会根据古老的习俗，在桥的一侧挂起一排共 $N$ 盏巨大的彩灯。

这些彩灯不仅照亮了泸江水面，更寄托了人们对风调雨顺的祈愿。

题目描述

今年灯会的主题是“红河韵味”，每盏彩灯可以涂上三种代表性的颜色：

1. 紫陶褐色（代表著名的建水紫陶）
2. 梯田金黄（代表哈尼梯田的丰收）
3. 苍翠石青（代表滇南的山水）

为了方便统计，我们将这三种颜色分别编号为 $1, 2, 3$。

然而，根据建水古老的营造法式，挂灯时有一个严格的禁忌：由于“紫陶褐色”色彩深沉，不能在相邻的两处位置同时悬挂编号为 $1$ 的彩灯（即序列中不能出现连续的两个 $1$）。

由于桥身很长，$N$ 的值可能很大。请你计算出，挂好这 $N$ 盏灯共有多少种不同的颜色组合方案？由于方案数可能极多，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

输入仅包含一个正整数 $N$，表示灯盏的总数。

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

22

样例 #2

样例输入 #2

10

样例输出 #2

24960

数据范围与提示

• 对于 $30\%$ 的数据：$1 \le N \le 20$。
• 对于 $60\%$ 的数据：$1 \le N \le 5000$。
• 对于 $100\%$ 的数据：$1 \le N \le 10^6$。