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
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
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.
3
2
1000000007
Returns: 11
10
4
1000000007
Returns: 157773
1000000000
1000
1000000009
Returns: 629516825
892314287
1808
1999993927
Returns: 1374427440
59380716
1330
1999998893
Returns: 643595096
3919002
755
1999993651
Returns: 1683094091
602841311
1650
1999997777
Returns: 1385816265
144294055
244
1999990763
Returns: 157066813
128538656
1589
1999999499
Returns: 1322382899
643890236
1651
1999992653
Returns: 378430270
373805363
1570
1999998457
Returns: 1829336147
288398590
930
1999990247
Returns: 167698557
738003421
277
1999991863
Returns: 1052762106
521871057
1562
1999995131
Returns: 521289000
547808803
178
1999994963
Returns: 895093171
25400283
813
1999995427
Returns: 123806366
596104778
1294
1999998443
Returns: 1780781849
583789697
844
1999999423
Returns: 636860196
84808407
950
1999989391
Returns: 452115254
291221863
831
1999997957
Returns: 1939894470
535533200
1502
1999999271
Returns: 139263876
230091123
588
1999990411
Returns: 1672301738
966867064
1107
1999999747
Returns: 1940660969
187313610
1995
1999996751
Returns: 1093406468
332629974
1980
1999989923
Returns: 1596097669
620057552
1916
1999991069
Returns: 184962831
205269550
1960
1999990009
Returns: 28455379
288824107
1931
1999989209
Returns: 1698632452
1000000000
2000
1999998479
Returns: 1125935433
1000000000
0
1000000007
Returns: 1
1
0
1000000007
Returns: 1
4000
2000
1000000007
Returns: 33872715
4001
2000
1000000007
Returns: 766745637