测试数据来自 system/1073

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

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

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

格式

输入格式

一个正整数n。（0<n<=50000）

输出格式

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

样例1

样例输入1

2

样例输出1

3

限制

来源

huyichen