1069. 4-Hanoi-Tower

时间限制 1000 ms
内存限制 128 MB

题目描述

“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有4根柱子, 而不是3根,那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?

为了编程方便,您只需要输出这个结果mod 10000的值。

输入数据

一个正整数 $n$ 。 $\ (0< n< 5\times10^{3})$

输出数据

一个正整数,表示把 $n$ 个盘子从第 $1$ 根柱子移动到第 $4$ 根柱子需要的最少移动次数mod10^{3}的值。

样例输入

2

样例输出

4

题目信息

未提交
未通过无法查看
未通过无法查看