Perfect Square Republic

The people of the Perfect Square Republic celebrate their Independence Day every year. However, independence happened so long ago that no one remembers the exact date anymore. All that remains in people's memory is the following.

• The number of days $D$ from Independence Day until today is a perfect square.
• $D$ can be written as a product of distinct natural numbers that are each at most $n$.
• $D$ is the largest number satisfying the two conditions above.

Because one year in this republic lasts $1{,}000{,}000{,}007$ days, the people want to know $D$ modulo $1{,}000{,}000{,}007$. Note that they want the remainder of the largest $D$ itself, not the largest possible remainder.

For each $n$, write a program that prints the largest such $D$ modulo $1{,}000{,}000{,}007$.

The input consists of several test cases. Each test case is a single line containing one integer $n$. ($1 \le n \le 10{,}000{,}000$)

The input ends when $0$ is given.

For each test case, print the largest valid $D$ modulo $1{,}000{,}000{,}007$, one value per line.