四塔问题
| 成绩 | 100 | 开启时间 | 2020年02月19日 星期三 14:35 |
| 折扣 | 0.8 | 折扣时间 | 2020年02月19日 星期三 14:35 |
| 允许迟交 | 是 | 关闭时间 | 2020年02月19日 星期三 14:35 |
| 输入文件 | hanoi4.in | 输出文件 | hanoi4.out |
【题目描述】四塔问题（hanoi4）
四塔问题中，柱子一共有4根，而不是3根，那么至少需要移动圆盘多少次，才能把所有的圆盘从第1根柱子移动到第4根柱子上呢？
为了编程方便，你只需输出这个结果%10 000的值。
【输入格式】
该题含有多组测试数据，每组一个正整数N（0＜N≤50 000）。
【输出格式】
一个正数，表示把N个圆盘从第1根柱子移动到第4根柱子需要的最少移动次数%10 000的值。
【输入样例】
15
【输出样例】
129