Number Decomposition

Time limit2sMemory limit128 MB

Summary
Given N up to 1,000,000, decompose it into nonnegative integers whose sum is N to maximize the product, then output that product mod 10007.
Level

Medium4 of 10

Topics
Math, Greedy, Number theory
Solved
No attempts yet

Problem

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.

Input

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

Output

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

Examples5

  1. Example 1

    Input
    7
    Expected output
    12

  2. Example 2

    Input
    0
    Expected output
    0

  3. Example 3

    Input
    1
    Expected output
    1

  4. Example 4

    Input
    5
    Expected output
    6

  5. Example 5

    Input
    9931
    Expected output
    4664