Problem Statement
You are given two positive
You are going to choose x distinct integers, each between 1 and n, inclusive. The choice will be made uniformly at random. That is, each of the possible x-element subsets of the integers 1 to n is equally likely to be chosen.
Let S be the smallest integer among the x chosen ones. Let P be the expected value of 2^S. (In other words, P is the average value of 2 to the power of S, where the average is taken over all possible choices of the x distinct integers.)
It can be shown that P * (n choose x) is an integer. Compute and return this integer, modulo 10^9 + 7.
Definition
- Class:
- ExpectedMinimumPower
- Method:
- findExp
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int findExp(int n, int x)
- (be sure your method is public)
Notes
- In the statement, "(n choose x)" denotes the corresponding binomial coefficient - i.e., the number of ways to choose an x-element subset of a n-element set.
Constraints
- n will be between 1 and 10^9.
- x will be between 1 and min(n, 10^6).
Examples
4
4
Returns: 2
You have to choose all four numbers. Thus, S will be 1 and P will be 2^1 = 2.
3
2
Returns: 8
There are three equally likely scenarios: you will select either {1,2} or {1,3} or {2,3}. The corresponding values of S are 1, 1, and 2, respectively, and therefore P = 8/3. You should return the value P*(3 choose 2) = P*3 = 8.
3
1
Returns: 14
10
4
Returns: 1696
1000000000
1000000
Returns: 799728241
30692575
371934
Returns: 64828167
199218900
985105
Returns: 565787630
493624865
738911
Returns: 876864736
45421581
87132
Returns: 186977161
610618262
467364
Returns: 51175049
412375698
775793
Returns: 135777925
679114074
570658
Returns: 460535584
271234790
276107
Returns: 957611334
921425578
929719
Returns: 589251897
454861659
195887
Returns: 479664985
234234234
234
Returns: 121714498
1000000000
1
Returns: 281250000
1000000
1000000
Returns: 2
1000000000
2
Returns: 281250014
1000000000
10
Returns: 281256218