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 (\textbf{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 \textbf{n}. As the years in Remoteland have \textbf{1000000007} days, their citizens just need \textbf{D }modulo \textbf{1000000007}. Note that they are interested in the largest \textbf{D}, not in the largest \textbf{D }modulo \textbf{1000000007}. \InputFile Every test case is described by a single line with an integer \textbf{n}, (\textbf{1} ≤ \textbf{n} ≤ \textbf{10000000}). The input ends with a line containing \textbf{0}. \OutputFile For each test case, output the number of days ago the Republic became independent, modulo \textbf{1000000007}, one per line.