在遥远的东方大陆有一个王国，这里的国王沉迷于数论的知识。他给手下的大臣发放俸禄的方法也很奇怪，具体如下：
大臣们在每个月都会积累一定的贡献值，然而国王需要让大臣自己算出本月的俸禄，计算的方法就是把贡献值分成若干个正整数相加：
，
这若干个正整数的乘积就是俸禄，然而分解的方法很多，每个人都想拿到最多的俸禄，请你编写一个程序，帮大臣们计算一下。
国王想了想，最后的答案可能比较大，国库支撑不了这么大的开支，所以需要对结果模1000007。
一个正整数，表示大臣当月的贡献值
一个整数，表示能获取的最大俸禄
样例输入
10
样例输出
36
样例解释
有很多种分解方案：
，答案：
……
经过计算分析，最大的结果是：36
1