JOIN

 Problem Statement

Problem Statement for CandyDrawing

### Problem Statement

There are N boxes, numbered 1 through N. For each i, box i contains exactly i candies and one pebble. Thus, there are exactly i+1 objects in box i.

We are now going to create a collection of N objects using the following simple procedure: from each box, we will draw one object uniformly at random.

Let p be the probability that our collection will contain exactly K candies. You are given the ints N, K, and MOD. Return the value (p * (N+1)!) modulo MOD.

### Definition

 Class: CandyDrawing Method: findProbability Parameters: int, int, int Returns: int Method signature: int findProbability(int N, int K, int MOD) (be sure your method is public)

### Constraints

-N will be bewteen 1 and 1,000,000,000 (inclusive).
-K will be between 0 and 2,000 (inclusive).
-MOD will be between 1,000,000,000 and 2,000,000,000 (inclusive).
-MOD will be a prime.

### Examples

0)

 `2` `1` `1000000007`
`Returns: 3`
 We have two boxes: box 1 with a candy and a pebble, and box 2 with two candies and a pebble. We are looking for the probability of drawing exactly one candy. This can happen in two different ways: either we draw the candy from box 1 and the pebble from box 2, or vice versa. The probability of the first way is (1/2)*(1/3) = 1/6. The probability of the second way is (1/2)*(2/3) = 1/3. Thus, the total probability is p = 1/6 + 1/3 = 1/2. We have p * (N+1)! = p*6 = 3, therefore the answer is (3 mod 1,000,000,007) = 3.
1)

 `3` `2` `1000000007`
`Returns: 11`
2)

 `10` `4` `1000000007`
`Returns: 157773`
3)

 `1000000000` `1000` `1000000009`
`Returns: 629516825`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 629 Round 1 - Division I, Level Three