시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 127 33 23 21.905%

문제

백준 공화국 사람들은 매년 독립일을 기념한다. 그러나 독립이 아주 오래 전의 일이었으므로, 이젠 독립일을 정확하게 기억하는 사람은 아무도 없다. 사람들의 기억속에 남아있는 것은 독립일로부터 오늘까지의 날 수 (D) 가 완전제곱수라는 사실, 그리고 그 수가 n이하의 서로 다른 자연수의 곱으로 이루어졌고, 가능한 가장 큰 수라는 사실이다.

백준 공화국은 1년이 1,000,000,007일 이므로 사람들은 D를 1,000,000,007로 나눈 나머지가 필요하다. 다만, D를 1,000,000,007로 나눈 나머지가 가장 큰 것이 아니라 D가 가장 큰 것을 원한다.

입력

각 테스트케이스마다 한 줄 씩 n이 주어진다(1 ≤ n ≤ 10, 000, 000). 입력으로 0이 들어오면 종료한다.

출력

각 테스트케이스마다 한 줄 씩 D를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

4
9348095
6297540
0

예제 출력

4
177582252
644064736

힌트