PrizeAward

PROBLEM STATEMENT

After much deliberation, TopCoder decided to do away with coder ratings.  As a
result of this decision, TopCoder was presented with two new problems.

One problem was that they needed to develop a new way of assigning coders to
rooms.  Many ideas were tossed around the conference table including random
assignment, and assignment by order of event registration.  In the end, no
solution could be agreed upon until one staff member suggested that all coders
compete in the same room.  Everyone seemed to like this idea and agreed that it
was the way to go.

The second problem was that the old system for breaking ties used coder ratings
to determine a winner.  Without coder ratings the old system was no longer
applicable.  Again, ideas were thrown back and forth without generating much
enthusiasm until the same staff member made a seemingly brilliant suggestion.
She thought it would be perfectly acceptable to allow ties if the prize money
was split fairly.  Everyone liked this idea, too.  TopCoder quickly deduced
that the fairest way to split prize money would be to take the sum of the
prizes and divide it equally among the tied coders.

For example, if coders A and B were tied for second place, the prize money for
second and third place would be added together and divided equally between
coders A and B.  The coder(s) with the next highest point total would be in
fourth place.

Your task is to calculate how many different ways prizes can be awarded given
the number of prizes and the number of coders (represented by n).  Keep in mind
that ties can be 2-way, 3-way, or even n-way, but coders cannot take more than
one place in a competition.

Remember, there can be more than one tie in a competition.


DEFINITION

Class: PrizeAward
Method: numWays
Parameters: int, int
Returns: long
Method signature (be sure it is declared public): long numWays(int prizes, int
coders);


NOTES

*In the event that "prizes" > "coders", only "coders" prizes will be awarded.
*The long data type is a 64-bit signed integer.

Note for C++ coders: The long data type is specific to the gcc compiler.


TopCoder will ensure the validity of all inputs.
Inputs are valid if all of the following criteria are met:
* prizes will be between 0 and 15 inclusive
* coders will be between 0 and 15 inclusive


EXAMPLES

0) prizes = 2
   coders = 4
   returns: 39

If the number of prizes is 2 and the number of coders is 4, how many different
ways can prizes be awarded?

First, there are 12 different ways to award prizes if there are no ties for
first or second place (each coder is represented by a letter):
Coder A could take first place with coder B coming in second place, this is
represented by: (A,B)
Other legal permutations are: (A,C) (A,D) (B,A) (B,C) (B,D) (C,A) (C,B) (C,D)
(D,A) (D,B) (D,C)

There are 6 different ways to award prizes if there is a 2-way tie for first
place:
Coders A and B could tie for first place as represented by: (A+B)
Other legal combinations are: (A+C) (A+D) (B+C) (B+D) (C+D)
Note that (A+C) is equivalent to (C+A), therefore it is only counted once.

There are 12 different ways to award prizes if there is a 2-way tie for second
place:
(A,B+C) (A,B+D) (A,C+D) (B,A+C) (B,A+D) (B,C+D) (C,A+B) (C,A+D) (C,B+D) (D,A+B)
(D,A+C) (D,B+C)

There are 4 different ways to award prizes if there is a 3-way tie for first
place:
(A+B+C) (A+B+D) (A+C+D) (B+C+D)

Similarly, there are 4 different ways to award prizes if there is a 3-way tie
for second place:
(A,B+C+D) (B,A+C+D) (C,A+B+D) (D,A+B+C)

Finally, all coders could tie for first place and share the total prize purse
evenly:
(A+B+C+D)

12 + 6 + 12 + 4 + 4 + 1 = 39

There are 39 possible ways to award prizes if there are four coders and two
prizes.
So, your method should return 39

1) prizes = 4
   coders = 9
   returns: 84109

2) prizes = 9
   coders = 4
   returns: 75

3) prizes = 0
   coders = 3
   returns: 1

4) prizes = 15
   coders = 0
   returns: 1