음이 아닌 정수 N을 한 개 이상의 음이 아닌 정수의 합으로 나타낼 때, 이를 "N을 분해한다"라고 부르자.</p>

예를 들어, 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로 나눈 나머지를 출력한다.

예제 입력 1

7

예제 출력 1

12

예제 입력 2

0

예제 출력 2

0

예제 입력 3

1

예제 출력 3

1

예제 입력 4

5

예제 출력 4

6

예제 입력 5

9931

예제 출력 5

4664