RMTLAND - Remoteland

In the Republic of Remoteland, the people celebrate their independence day every year. However, as it was a long long time ago, nobody can remember when it was exactly. The only thing people can remember is that today, the number of days elapsed since their independence (D) is a perfect square, and moreover it is the largest possible such number one can form as a product of distinct numbers less than or equal to n.

As the years in Remoteland have 1,000,000,007 days, their citizens just need D modulo 1,000,000,007. Note that they are interested in the largest D, not in the largest D modulo 1,000,000,007.

Input

Every test case is described by a single line with an integer n, (1 ≤ n ≤ 10,000,000). The input ends with a line containing 0.

Output

For each test case, output the number of days ago the Republic became independent, modulo 1,000,000,007, one per line.

Sample Input

4
9348095
6297540
0

Sample Output

4
177582252
644064736

Problemsetter: Javier Gómez Serrano

Added by:David García Soriano
Date:2011-11-26
Time limit:2.074s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Southwestern Europe Regional, SWERC 2011

hide comments
2014-05-28 20:00:02 EsVee
Does the problem demand an O(n) Solution?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.