수 분해
시간 제한2초메모리 제한128 MB
N(최대 1,000,000)을 자연수들의 합으로 분해할 때 곱이 최대가 되는 값을 구해 10007로 나눈 나머지를 출력합니다.
문제
음이 아닌 정수 N을 하나 이상의 음이 아닌 정수의 합으로 나타내는 것을 N의 분해라고 하자.
예를 들어 4는 1+1+1+1, 1+1+2, 1+3, 2+2, 4처럼 분해할 수 있다.
분해 곱은 분해에 사용된 모든 수를 곱한 값이다. N=4일 때 각 분해의 곱은 다음과 같다.
- 1+1+1+1의 곱은 1이다.
- 1+1+2의 곱은 2이다.
- 1+3의 곱은 3이다.
- 2+2의 곱은 4이다.
- 4의 곱은 4이다.
N이 주어졌을 때, 가능한 분해 곱의 최댓값을 구하라.
입력
첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다.
출력
첫째 줄에 N의 분해 곱의 최댓값을 10,007로 나눈 나머지를 출력한다.