Number Decomposition

Representing a nonnegative integer N as the sum of one or more nonnegative integers is called a decomposition of N.

For example, 4 can be decomposed as 1+1+1+1, 1+1+2, 1+3, 2+2, or 4.

The decomposition product is the product of all numbers used in the decomposition. For N=4, the products are as follows.

• The product of 1+1+1+1 is 1.
• The product of 1+1+2 is 2.
• The product of 1+3 is 3.
• The product of 2+2 is 4.
• The product of 4 is 4.

Given N, find the maximum possible decomposition product.

The first line contains a nonnegative integer N. N is at most 1,000,000.

Print the remainder when the maximum decomposition product of N is divided by 10,007.