### Problem Statement

You are given two positive integers, sum and count. Consider all possible ways to express sum as a sum of exactly count positive integers. Two ways are considered equal if we can obtain one from the other by changing the order of the summed numbers. For example, 8=3+2+1+1+1 is the same as 8=1+3+1+2+1, but not the same as 8=3+2+2+1. Thus we will only be interested in such summations where the summed integers are in non-increasing order.

For example, if sum=8 and count=3, the possible ways are:

```8 = 6+1+1
8 = 3+3+2
8 = 4+2+2
8 = 4+3+1
8 = 5+2+1
```

We may now order these summations in the following way: Order them according to the first summand in decreasing order. In case of a tie, order them according to the second summand, etc. In general, to compare two summations, look at the first summand where they differ. The one where this summand is larger will be earlier in our order.

For our previous example, the correct order is:

```8 = 6+1+1
8 = 5+2+1
8 = 4+3+1
8 = 4+2+2
8 = 3+3+2
```

You will be given three ints: sum, count and index, where index contains a zero-based index of a summation in the order defined above. Your method should return a String containing that summation in the form "SUM=SUMMAND(1)+...+SUMMAND(count)". If index is too large to specify a valid summation, return an empty string.

### Definition

 Class: FixedSizeSums Method: kthElement Parameters: int, int, int Returns: String Method signature: String kthElement(int sum, int count, int index) (be sure your method is public)

### Notes

-You may assume that the total number of possible summations will never exceed 2,000,000,000.

### Constraints

-sum is between 1 and 150, inclusive.
-count is between 1 and 150, inclusive.
-index is between 0 and 2,000,000,000, inclusive.

### Examples

0)

 `8` `3` `2`
`Returns: "8=4+3+1"`
 This is the example from the problem statement. Look at the ordered list of possible summations and number them starting with zero.
1)

 `13` `1` `0`
`Returns: "13=13"`
 There is only one possibility here.
2)

 `13` `13` `0`
`Returns: "13=1+1+1+1+1+1+1+1+1+1+1+1+1"`
 Again, there is only one possible summation.
3)

 `7` `10` `3`
`Returns: ""`
 This is impossible. A sum of 10 positive integers is never equal to 7.
4)

 `17` `2` `4`
`Returns: "17=12+5"`
 The first five possible summations are: "17=16+1", "17=15+2", "17=14+3", "17=13+4", and "17=12+5".
5)

 `140` `17` `87654321`
`Returns: "140=40+31+15+15+9+7+4+4+2+2+2+2+2+2+1+1+1"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6015

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9808&pm=6015

misof

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming, Math, Sorting