《算法竞赛宝典》基础算法艺术(公开课程)

【问题描述】(hanoi4.cpp/c/pas)

墨老师：“现在可以了吗？”

楚继光：“开始是压制住了修罗王的魔法炮阵，但现在修罗王又加强了火力。”

墨老师：“那就用四塔防御系统好了。”

四塔防御系统一共有4根柱子，而不是3根，那么至少需要移动能量盘多少次，才能把所有的能量盘从第1根柱子移动到第4根柱子上呢？

为了编程方便，你只需输出这个结果%10000的值。

【输入格式】

该题含有多组测试数据，每组一个正整数N。（0<N≤50000）

【输出格式】

一个正数，表示把N个能量盘从第1根柱子移动到第4根柱子需要的最少移动次数%10000的值。

【输入样例】

15

【输出样例】

129