시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 168 33 27 23.276%

문제

음이 아닌 정수 N을 분해한다는 합이 N이되는 몇 개의 음이 아닌 정수로 나타낸다는 말이다.

예를 들어, 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4 로 나눌 수 있다.

분해 곱이란 N을 분해해서 나타난 수들을 전부 곱한 것을 의미한다. N=4일 때, 분해 곱은 다음과 같다.

  • 4 = 1+1+1+1, 곱 : 1*1*1*1 = 1
  • 4 = 1+1+2, 곱 : 1*1*2 = 2
  • 4 = 1+3, 곱 : 1*3 = 3
  • 4 = 2+2, 곱 : 2*2 = 4
  • 4 = 4, 곱 : 4

N이 주어졌을 때, 그 수의 분해 곱의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 수의 분해 곱의 최대값을 10,007로 나눈 나머지를 출력한다.

예제 입력

7

예제 출력

12

힌트

7 = 3+4, 12 = 3*4

출처