수 분해

음이 아닌 정수 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로 나눈 나머지를 출력한다.