题目来源：@

DSES站台序列构造

题目描述

@ 正在建造一条贯穿猎户旋臂的星际传送轨道，轨道上依次排布着 $n$ 座连续星际站台，编号依次为 $1，2，3...n$。 需要为每一座站台配置一种能量核心，可供选择的核心一共有四种类型：do核心（A）、something核心（B）、earth核心（C）、shaking核心（D）。 出于星际能量平衡法则，轨道存在多条硬性安全约束，任何违反约束的配置方案都会引发能量风暴，导致整条传送轨道瘫痪。经过Do something Earth-shaking无数次模拟实验，总结出如下不可违背的限制规则： do核心限制：不允许存在两座相邻站台同时搭载do核心（不能出现连续 AA）； something核心限制：任意一段连续排布的something核心，其连续数量最多只能有 3 个。也就是说序列中不能出现 BBBB，连续 1 个 B、2 个 B、3 个 B 都是合法形式； earth核心限制：如果某一站台使用earth核心，那么它前一个站台不能使用do核心； shaking核心无额外限制，可以和任意核心相邻，连续放置也完全允许。 现在Do something Earth-shaking想要知道，对于拥有 n 座站台的轨道，一共有多少种互不相同、满足全部安全规则的核心配置方案。 由于最终的方案数量会极其庞大，数值远远超出普通整数存储范围，你只需要输出方案总数对 1e9+7 取模之后的结果。 输入格式输入仅一行，包含一个正整数 n，代表星际站台总数。输出格式输出一行一个整数，表示合法配置方案数量模 1e9+7 的结果。

样例说明:

1

4

解释：只有 1 座站台，可以选 A/B/C/D，共 4 种方案。

2

14

数据范围与约定

• $1\le n\le 2\times 10^6$