완전제곱 공화국

완전제곱 공화국 사람들은 매년 독립일을 기념한다. 그러나 독립이 아주 오래전 일이라서, 이제는 독립일을 정확히 기억하는 사람이 아무도 없다. 사람들의 기억에 남아 있는 사실은 다음과 같다.

• 독립일로부터 오늘까지의 날 수 $D$는 완전제곱수이다.
• $D$는 $n$ 이하의 서로 다른 자연수들의 곱으로 나타낼 수 있다.
• $D$는 위 두 조건을 만족하는 가장 큰 수이다.

이 공화국은 1년이 $1{,}000{,}000{,}007$일이므로, 사람들은 $D$를 $1{,}000{,}000{,}007$로 나눈 나머지를 알고 싶어 한다. 단, 나머지가 가장 큰 것이 아니라 $D$ 자체가 가장 큰 경우의 나머지를 구해야 한다.

각 $n$에 대해, 조건을 만족하는 가장 큰 $D$를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 정수 $n$ 하나로 주어진다. ($1 \le n \le 10{,}000{,}000$)

$0$이 입력되면 입력이 끝난다.

각 테스트 케이스마다, 조건을 만족하는 가장 큰 $D$를 $1{,}000{,}000{,}007$로 나눈 나머지를 한 줄에 하나씩 출력한다.