AlvinZH叕掉坑里了

题目描述

AlvinZH叕掉进坑里了！

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

假设现在AlvinZH捡到了n块金币，他一共带了很多个背包，每个背包可以装任意多金币，这一次AlvinZH任性了，他想随便装：随便装多少个袋子，袋子里随便装多少个金币。

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

注：所有背包看作相同，即{1,3}和{3,1}是同一种方法。

难题慎入

输入

输入包含多组数据。

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

输出

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

输入样例

4
6

输出样例

5
11

样例解释

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

HINT

这更不是简单的背包问题了，甚至不是背包问题，这和大数学家欧拉有关~