题目描述

SIMO放假来到了一家店做临时工，一个月后，老板要开始给希蒙算工资了，具体算法如下：

员工在每个月都会积累一定的贡献值$n$，然而老板比较懒，他希望员工能自己算出工资，老板想了一个工资结算的方法：

就是先把贡献值$n$分成若干个正整数相加。即：$n = a_1+a_2+a_3+…+a_m$

然后这若干个正整数的乘积 $(a_1*a_2*...*a_m)$ 就是这个月的工资，然而分解的方法很多，每个人都想拿到最多的工资，SIMO也不例外，请你编写一个程序，帮SIMO计算一下他最多能获得多少工资。

老板想了想，最后的答案可能比较大，自己的钱包支撑不了这么大的开支，所以需要对上述的结果模$10007$。

输入格式

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

输出格式

一个整数，表示这若干个数乘积取余 $10007$ 后的结果。

样例数据

10

36

11

54

100

7589

提示

对于100%的数据，$1 \leq n \leq 3*10^8$

样例解释1：10有很多分法，但 $10 = 2+2+3+3$ 这种情况下答案最大，为 $2*2*3*3=36$

样例解释2：11有很多分法，但 $11 = 2+3+3+3$ 这种情况下答案最大，为 $2*3*3*3=54$