题目描述

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

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

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

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

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

输入格式

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

输出格式

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

样例

输入样例

15

输出样例

129