JOIN
Get Time

   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