Problem Description

环形汉诺塔 (Circular Hanoi)

题目背景

在传统的汉诺塔问题中，盘子可以在任意两根柱子之间移动。但小 W 最近发明了一种“新型汉诺塔”玩具，由于机械结构的限制，盘子只能按照固定的单向环形轨道滑动。

题目描述

游戏初始时，有 $n$ 个大小不一的盘子按照从大到小、从下到上的顺序堆叠在柱子 $A$ 上。现在共有 $A, B, C, D$ 四根柱子，你每次只能将某根柱子最顶端的盘子移动到相邻的下一根柱子上。

具体的单向移动规则为：$A \to B \to C \to D \to A$，即只能按照顺时针方向依次移动，绝对不允许逆向移动，也不允许跨越柱子移动。

同时，必须时刻遵循汉诺塔的核心规则：在任何一根柱子上，大盘子绝对不能压在小盘子上面。

小 W 想知道，在遵守上述所有规则的前提下，将这 $n$ 个盘子作为一个整体，从柱子 $A$ 移动到柱子 $D$（即顺时针移动 3 步），最少需要多少次移动？

由于答案可能非常大，请将最终的最少移动步数对 $10^9+7$ 取模后输出。

输入格式

输入共一行，包含一个正整数 $n$，表示盘子的总数。

输出格式

输出一行一个整数，表示将 $n$ 个盘子从 $A$ 柱移动到 $D$ 柱的最少步数对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

1

输出 #1

3

输入输出样例 #2

输入 #2

2

输出 #2

10

说明/提示

【样例解释 #1】 只有一个盘子时，移动路径为 $A \to B$, $B \to C$, $C \to D$，共计 $3$ 步。

【样例解释 #2】 当有 $2$ 个盘子时（小盘为 $1$，大盘为 $2$），最优移动序列如下：

1. 盘 $1$：$A \to B \to C$ （2步，盘 1 停在 C）
2. 盘 $2$：$A \to B$ （1步，盘 2 停在 B）
3. 盘 $1$：$C \to D \to A$ （2步，盘 1 停在 A）
4. 盘 $2$：$B \to C \to D$ （2步，盘 2 停在 D）
5. 盘 $1$：$A \to B \to C \to D$ （3步，盘 1 停在 D）。

【数据规模与约定】

为了提供更好的区分度，本题共设置 10 个测试点。

| 测试点编号 | $n \le$ | 分值 | | --- | --- | --- | --- | | $1 \sim 2$ | $5$ | $20$ | | $3 \sim 5$ | $20$ | $30$ | | $6 \sim 10$ | $10^7$ | $50$ |

对于 $100\%$ 的数据，保证 $1 \le n \le 10^{7}$。