204021 - 四塔问题

四塔问题中，放有圆盘的柱子一共有4根，而不是3根，每次只能移动一个圆盘，每个柱子的圆盘保持上小下大的顺序，那么至少需要移动圆盘多少次，才能把所有的圆盘从第1根柱子移动到第4根柱子上呢？ 为了编程方便，你只需输出这个结果%10 000的值。

输入包含有多组测试数据，每组一个正整数N（0＜N≤50 000）。

输出一个正数，表示把N个圆盘从第1根柱子移动到第4根柱子需要的最少移动次数%10 000的值。