说明

     一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数（Pefect Sqaure），也称平方数。
小A认为所有的平方数都是很perfect的~ 
     于是他给了小B一个任务：用任意个不大于n的不同的正整数相乘得到完全平方数，并且小A希望这个平方数越大越好。
请你帮助小B告诉小A满足题意的最大的完全平方数。

输入格式

输入仅 1行，一个数n。

输出格式

输出仅1行，一个数表示答案。由于答案可以很大，所以请输出答案对100000007取模后的结果。

样例

7

144

提示

【输入输出样例解释1】
144=2×3×4×6，是12的完全平方。
【输入输出样例2】
number.in  
9
number.out
5184
【输入输出样例解释2】
5184=3×4×6×8×9，是72的完全平方。
对于50%的数据，0<n≤5,000； 
对于70%的数据，0<n≤100,000； 
对于100%的数据，0<n≤5,000,000。