Problem 4C. 赌徒默示录

时间限制：1000ms

空间限制：256MB

题目描述

走头无路的浩渡波来到了澳门，身无分文的他在街边捡到了一元硬币。于是他兴起走进了一个馆子玩玩“游戏”。
这个“公平的游戏“，规则是这样的，抛出一枚公平的硬币，有一半的概率投到正面，那么浩渡波获得一元硬币。还有另一半概率投到反面，浩渡波就会失去一元硬币。当他把硬币输光时，游戏提前结束。现在要你计算一下经过n轮（包括n轮前就输光），最后有多大的概率血本无归，并以此对他提出建议。（由于结果为小数，因此输出硬币的期望数量乘上2的n次方。请给出答案模上100007的余数。）

输入格式

一个整数n，表示玩了至多n轮。

输出格式

一个整数，表示期望硬币数。

样例输入1

3

样例输出1

5

样例1解释

输光的概率：\(0.5+0.5^3=0.625\)。
结果为 \(0.625*2^3=5\)

数据范围及约定

对于30%的数据 \(0 \le n \le 10\)。
对于100%的数据 \(0 \le n \le 1000\)。
Tips：假设庄家的钱无穷多，可以猜想一下n趋于无穷的结果。