Red Packet Expectation

In a red packet system, you are given a total of \(w\) units of money. When a person grabs the red packet, the amount they receive, \(x\), is chosen uniformly at random from the interval \([0, w]\). Suppose there are \(n\) people who grab the red packet sequentially. The first person will grab an amount with an expected value of \(\frac{w}{2}\). After the first grab, the remaining amount becomes \(\frac{w}{2}\) in expectation. In general, the \(k\)-th person will grab an amount with an expected value of

[ E_k = \frac{w}{2^k} ]

Your task is to compute \(E_k \bmod (10^9+7)\). Note that although the grabbing process is random, the linearity of expectation lets us conclude that the \(k\)-th person’s expected value is \(\frac{w}{2^k}\), independent of the total number of people \(n\) (with the guarantee that \(1 \leq k \leq n\)).

inputFormat

The input consists of three integers (w), (n), and (k) separated by spaces, where (w) is the total amount of money in the red packet, (n) is the number of people, and (k) is the order of the person for whom the expected value is to be calculated. It is guaranteed that (1 \leq k \leq n).

outputFormat

Output a single integer representing (\frac{w}{2^k}) modulo (10^9+7). Since division under modulo is not straightforward, compute the result as (w \times (2^k)^{-1} \bmod (10^9+7)), using the modular inverse of (2^k).

sample

10 5 1

5