eolymp
bolt
Try our new interface for solving problems
Məsələlər

Remoteland

Remoteland

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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 1000000007 days, their citizens just need D modulo 1000000007. Note that they are interested in the largest D, not in the largest D modulo 1000000007.

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4
9348095
6297540
0
Çıxış verilənləri #1
4
177582252
644064736