题目描述

在遥远的东方大陆有一个王国，这里的国王沉迷于数论的知识。他给手下的大臣发放俸禄的方法也很奇怪，具体如下：

大臣们在每个月都会积累一定的贡献值$n$，然而国王需要让大臣自己算出本月的俸禄，计算的方法就是把贡献值$n$分成若干个正整数相加：

$n = a_1+a_2+a_3+a_4+……+a_m$，

这若干个正整数的乘积就是俸禄，然而分解的方法很多，每个人都想拿到最多的俸禄，请你编写一个程序，帮大臣们计算一下。

国王想了想，最后的答案可能比较大，国库支撑不了这么大的开支，所以需要对结果模1000007。

输入格式

一个正整数$n$，表示大臣当月的贡献值

输出格式

一个整数，表示能获取的最大俸禄

样例数据

10

36

解释：$10 = 2+2+3+3$，这种情况下答案最大

数据范围

1$\leq n \leq 1000$