提示: 欢迎访问OurACM平台
Problem 1036 四塔问题

Accept: 593    Submit: 1512
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

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

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

Input

该题含有多组测试数据,每组一个正整数n。(0<n<=50000)

Output

一个正整数,表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

Sample Input

15

Sample Output

129

Submit  Back  Status  Discuss