给你一个n，请在1～n之间任意选取若干个数字，每个数字最多能选一次，请把你选取的数字相乘，要求这个乘积必须为一个平方数，那么请就算出最大的符合条件的乘积，并对1000000007取余。

每行一个数字n（1<=n<=10000000)，以一个0结束。

输出答案，每个结果占一行。

4
9348095
6297540
0

4
177582252
644064736