시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 56 17 16 36.364%

문제

자연수 N의 약수란 N으로 나누어 나머지가 0이 되는 자연수들을 말한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다.

실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다.

SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1)+SOD(2)+…+SOD(n)이라고 하자.

CSOD(n)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1<=n<=200,000,000인 정수)

출력

첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.

예제 입력

100

예제 출력

3150

힌트