“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有 4 根柱子而不是 3 根，那么至少需要移动盘子多少次，才能把所有的盘子从第 1 根柱子移动到第 4 根柱子上呢？ 为了编程方便，您只需要输出这个结果 $\mod 10000$ 的值。

一个正整数 $n\ (0<n\le 50000)$。

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

2 \n

4 \n