Problem D
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
The input contains at most 25 testcases. Every test case is described by a single line with an integer $n$, ($1 \le n \le 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 1 | Sample Output 1 |
|---|---|
4 9348095 6297540 0 |
4 177582252 644064736 |