“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子， 而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？
为了编程方便，您只需要输出这个结果mod 10000的值。
input：
一个正整数n。（0<n<=50000）
output：
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。
input：
15
output：
129
分析：
1: 0+2^0=1;
2: 1+2^1=3;
3: 3+2^1=5;
4: 5+2^2=9;
5: 9+2^2=13;
6: 13+2^2=17;
7: 17+2^3=25;
7: 25+2^3=33;
8: 33+2^3=41;
9: 41+2^3=49;
10: 49+2^4=65;
【参考程序】：
var n,i,j,k,ans,tail,now:longint;
begin
while not eof do
begin
readln(n);
i:=0;j:=-1;
now:=0;tail:=1;
for k:=1 to n do
begin
now:=(now+tail) mod 10000;
inc(j);
if i=j then
begin
inc(i);
j:=-1;
tail:=(tail shl 1) mod 10000;
end;
ans:=now;
end;
writeln(ans);
end;
end.