时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
汉诺塔游戏有三根柱子，编号分别为1, 2, 3。1号柱子上有 
个穿孔圆盘，盘的尺寸由下到上依次变小。游戏的目标是将所有的圆盘从1号柱子移动到3号柱子，并且在移动过程中需要遵循以下规则：
小S觉得所有圆盘都在1号柱子的版本太简单了，于是他想了一个更复杂的版本：给定每个圆盘初始时所在的柱子编号，求将所有圆盘移动到3号柱子上所需的最小步数。小S并不会做这道题，于是他把这个问题交给了您。
由于答案可能很大，您只需要输出其对
取模的结果即可。
- 每次只能将某个柱子顶端的一个圆盘移动到任意一个其他柱子的顶端；
- 不允许将大圆盘放在小圆盘上面。
图1 n=3时的汉诺塔游戏
小S觉得所有圆盘都在1号柱子的版本太简单了，于是他想了一个更复杂的版本：给定每个圆盘初始时所在的柱子编号，求将所有圆盘移动到3号柱子上所需的最小步数。小S并不会做这道题，于是他把这个问题交给了您。
由于答案可能很大，您只需要输出其对
输入描述:
第一行一个正整数（
），表示圆盘的数量。
第二行
输出描述:
一行一个整数，表示所需的最小步数对取模的结果。
