A decomposition of a non-negative integer n is a list of non-negative integers that sum to exactly n. The product of a decomposition is the product of all its members. For example, if n = 4, the following decompositions are possible:
4 = 1+1+1+1, product is 1*1*1*1 = 1.
4 = 1+1+2, product is 1*1*2 = 2.
4 = 1+3, product is 1*3 = 3.
4 = 2+2, product is 2*2 = 4.
4 = 4, product is 4.
Given an int n, determine the decomposition of n with the maximal product, and return that product modulo 10007. In the example above, the maximal product is 4 (the product of the decomposition 2 + 2).
|