ExpectedMinimumPower | Topcoder Archive

Problem Statement

You are given two positive ints: n and x.

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
```

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)2024, Topcoder, Inc. All rights reserved.