测试数据来自 system/3022

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　古老的汉诺塔问题是：用最少的步数将 \(N\) 个半径互不相等的圆盘从 A 柱利用 B 柱全部移动到 C 柱，在移动过程中小盘始终在大盘的上面。现在再附加一个条件：任何时候都不允许直接把盘子从 A 柱移动到 C 柱，也不允许直接把盘子从 C 柱移动到 A 柱。

　　比如当 \(N=2\) 时，最少需要 8 步移动，过程如下（A柱上的两个盘子从上到下编号为1，2）：
　　●第1步：把1号盘 A 柱移到 B 柱子
　　●第2步：把1号盘 B 柱移到 C 柱子
　　●第3步：把2号盘 A 柱移到 B 柱子
　　●第4步：把1号盘 C 柱移到 B 柱子
　　●第5步：把1号盘 B 柱移到 A 柱子
　　●第6步：把2号盘 B 柱移到 C 柱子
　　●第7步：把1号盘 A 柱移到 B 柱子
　　●第8步：把1号盘 B 柱移到 C 柱子

【输入格式】

　　一个整数 \(N\)。　　

【输出格式】

　　输出最少移动步数 \(mod\ 10^9+3\)。

【输入输出样例】

　Input

4

　Output

80

【数据限制】

　　对于 \(100\%\) 的数据满足，\(1≤N≤10^{10}\)。

【来源】

　　Mr.he