시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 138 36 26 22.414%

문제

백준 공화국 사람들은 매년 독립일을 기념한다. 그러나 독립이 아주 오래 전의 일이었으므로, 이젠 독립일을 정확하게 기억하는 사람은 아무도 없다. 사람들의 기억속에 남아있는 것은 독립일로부터 오늘까지의 날 수 (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로 나눈 나머지를 출력한다.

예제 입력 1

4
9348095
6297540
0

예제 출력 1

4
177582252
644064736
W3sicHJvYmxlbV9pZCI6IjM4NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWM5MDAgXHVhY2Y1XHVkNjU0XHVhZDZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzFcdWM5MDAgXHVhY2Y1XHVkNjU0XHVhZDZkIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWI5ZTRcdWIxNDQmbmJzcDtcdWIzYzVcdWI5YmRcdWM3N2NcdWM3NDQgXHVhZTMwXHViMTUwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHViM2M1XHViOWJkXHVjNzc0Jm5ic3A7XHVjNTQ0XHVjOGZjIFx1YzYyNFx1Yjc5OCBcdWM4MDRcdWM3NTggXHVjNzdjXHVjNzc0XHVjNWM4XHVjNzNjXHViYmMwXHViODVjLCBcdWM3NzRcdWM4MjAmbmJzcDtcdWIzYzVcdWI5YmRcdWM3N2NcdWM3NDQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YWUzMFx1YzViNVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNTQ0XHViYjM0XHViM2M0IFx1YzVjNlx1YjJlNC4gXHVjMGFjXHViNzhjXHViNGU0XHVjNzU4IFx1YWUzMFx1YzViNVx1YzE4ZFx1YzVkMCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzQwJm5ic3A7XHViM2M1XHViOWJkXHVjNzdjXHViODVjXHViZDgwXHVkMTMwIFx1YzYyNFx1YjI5OFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWIwYTAgXHVjMjE4IChEKSBcdWFjMDAgXHVjNjQ0XHVjODA0XHVjODFjXHVhY2YxXHVjMjE4XHViNzdjXHViMjk0IFx1YzBhY1x1YzJlNCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWMyMThcdWFjMDAgblx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODRjXHVhY2UwLCZuYnNwO1x1YWMwMFx1YjJhNVx1ZDU1YyZuYnNwO1x1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMjE4XHViNzdjXHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwIFx1YWNmNVx1ZDY1NFx1YWQ2ZFx1Yzc0MCAxXHViMTQ0XHVjNzc0Jm5ic3A7MSwwMDAsMDAwLDAwN1x1Yzc3YyBcdWM3NzRcdWJiYzBcdWI4NWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIERcdWI5N2MmbmJzcDsxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWIyZTRcdWI5Y2MsIERcdWI5N2MmbmJzcDsxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjIERcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NDQgXHVjNmQwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0IFx1YzUyOSBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCgxICZsZTsgbiAmbGU7IDEwLCAwMDAsIDAwMCkuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyZuYnNwOzBcdWM3NzQgXHViNGU0XHVjNWI0XHVjNjI0XHViYTc0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDQgXHVjNTI5Jm5ic3A7RFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4NDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZW1vdGVsYW5kIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgUmVwdWJsaWMgb2YgUmVtb3RlbGFuZCwgdGhlIHBlb3BsZSBjZWxlYnJhdGUgdGhlaXIgaW5kZXBlbmRlbmNlIGRheSBldmVyeSB5ZWFyLiBIb3dldmVyLCBhcyBpdCB3YXMgYSBsb25nIGxvbmcgdGltZSBhZ28sIG5vYm9keSBjYW4gcmVtZW1iZXIgd2hlbiBpdCB3YXMgZXhhY3RseS4gVGhlIG9ubHkgdGhpbmcgcGVvcGxlIGNhbiByZW1lbWJlciBpcyB0aGF0IHRvZGF5LCB0aGUgbnVtYmVyIG9mIGRheXMgZWxhcHNlZCBzaW5jZSB0aGVpciBpbmRlcGVuZGVuY2UgKEQpIGlzIGEgcGVyZmVjdCBzcXVhcmUsIGFuZCBtb3Jlb3ZlciBpdCBpcyB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzdWNoIG51bWJlciBvbmUgY2FuIGZvcm0gYXMgYSBwcm9kdWN0IG9mIGRpc3RpbmN0IG51bWJlcnMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIG4uPFwvcD5cclxuXHJcbjxwPkFzIHRoZSB5ZWFycyBpbiBSZW1vdGVsYW5kIGhhdmUgMSwgMDAwLCAwMDAsIDAwNyBkYXlzLCB0aGVpciBjaXRpemVucyBqdXN0IG5lZWQgRCBtb2R1bG8gMSwgMDAwLCAwMDAsIDAwNy4gTm90ZSB0aGF0IHRoZXkgYXJlIGludGVyZXN0ZWQgaW4gdGhlIGxhcmdlc3QgRCwgbm90IGluIHRoZSBsYXJnZXN0IEQgbW9kdWxvIDEsIDAwMCwgMDAwLCAwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FdmVyeSB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIGJ5IGEgc2luZ2xlIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4sICgxICZsZTsgbiAmbGU7IDEwLCAwMDAsIDAwMCkuIFRoZSBpbnB1dCBlbmRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgbnVtYmVyIG9mIGRheXMgYWdvIHRoZSBSZXB1YmxpYyBiZWNhbWUgaW5kZXBlbmRlbnQsIG1vZHVsbyAxLCAwMDAsIDAwMCwgMDA3LCBvbmUgcGVyIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d