AlvinZH叒掉坑里了

题目描述

AlvinZH叒掉坑里了！

幸运的是，这坑竟然是宝藏迷宫的入口。这一次AlvinZH机智地带了很多很多背包——装金币！

假设现在AlvinZH捡到了n块金币，他一共带了很多个背包，每个背包可以装任意多金币，这一次AlvinZH允许有空的背包，但不允许有装了相同数量金币的背包。

请你帮他计算一下一共有多少种装金币的方法吧！

请注意内存限制。

输入

输入包含多组数据。

每组数据只含一个正整数，为金币数n（1≤n≤50000）。

输出

对于每组数据，输出一行，为装金币的方法数（结果对1000007取模）。

输入样例

4
6

输出样例

2
4

样例解释

4：{4}、{1,3}；

6：{6}、{1,5}、{2,4}、{1,2,3}。

HINT

这不是简单的背包问题，请勿套公式。