Problem Description

题目描述

游戏初始时，有 $n$ （1<=n<=1e18）个大小不一的盘子按照从大到小、从下到上的顺序堆叠在柱子 $A$ 上。现在共有 $A, B, C$ 三根柱子，每次操作可以将某根柱子最顶端的盘子移动到另一根柱子上，但需满足以下限制：

• $A$ 和 $B$ 之间不能直接移动，即不允许 $A \to B$ 和 $B \to A$ 的操作。所有涉及 $A$ 和 $B$ 的移动都必须借助柱子 $C$ 中转。
• 必须时刻遵循汉诺塔的核心规则：在任何一根柱子上，大盘子绝对不能压在小盘子上面。

小 W 想知道，在遵守上述规则的前提下，将这 $n$ 个盘子全部从柱子 $A$ 移动到柱子 $C$，最少需要多少次移动？

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

输入格式

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

输出格式

输出一行一个整数，表示最少移动步数对 $10^9+7$ 取模的结果。

提示

样例 1 解释

只有一个盘子时，直接从 $A \to C$，共 $1$ 步。

样例 2 解释

当有 $2$ 个盘子时（小盘为 $1$，大盘为 $2$），最优移动序列如下：

1. 盘 $1$：$A \to C$
2. 盘 $1$：$C \to B$
3. 盘 $2$：$A \to C$
4. 盘 $1$：$B \to C$

共计 $4$ 步。

1

1

2

4

3

13

Source

原创