Background

Redbag invented a redbag-grabbing system.

Problem Description

This redbag-grabbing system works like this: suppose there are currently $w$ yuan. Then the amount of money you can get from grabbing a redbag is a real number $x$ chosen uniformly at random from $[0,w]$ with equal probability.

Now Redbag releases a redbag worth $w$ yuan, and there are $n$ people grabbing it. What is the expected amount of money that the $k$-th person will get?

Output the result modulo $10^9+7$.

Input Format

One line with three integers, $w,n,k$.

Output Format

Output the expected amount of money the $k$-th person gets, taken modulo $10^9+7$.

Note: The expectation may be a fraction. For how to take a fraction modulo, you can search online (Du Niang).

2 1 1

1

Hint

Note that Redbag’s redbag-grabbing system is different from WeChat’s redbag system. In Redbag’s system, the money is not necessarily an integer number of cents.

• For $30\%$ of the testdata, $k=1$.
• For another $30\%$ of the testdata, the expectation is an integer before taking modulo, and $k\le 10$.

For all testdata, $0< w< (10^9+7)$, $n\le 10^{18},k\le n$.

Translated by ChatGPT 5