시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 389 | 174 | 92 | 34.848% |
백준 공화국 사람들은 매년 독립일을 기념한다. 그러나 독립이 아주 오래 전의 일이었으므로, 이젠 독립일을 정확하게 기억하는 사람은 아무도 없다. 사람들의 기억속에 남아있는 것은 독립일로부터 오늘까지의 날 수 (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
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2011 J번