P6026 Restaurant

Xiao W’s family has just opened a new restaurant.

The restaurant offers $n$ signature dishes, numbered $1,2,\cdots,n$. One day, $k$ customers came to the restaurant, and they had not decided what to eat. So Xiao W gave them an idea: each person first randomly chooses a number $r$ from $1,2,\cdots,n$ with equal probability, then randomly chooses a number $l$ from $1,2,\cdots,r$ with equal probability. This person then orders all dishes with numbers between $l$ and $r$ (including $l$ and $r$). So the customers did as Xiao W said. After all customers finished ordering, Xiao W suddenly realized: no two people ordered the same dish, so he only needs to cook at most one portion of each dish. To prove how lucky he is, he found you, who studies programming, and asks you to help compute the probability that this situation happens.

Two integers $n$ and $k$, as described in the statement.

Output one integer $p$, which is the required probability modulo $10^9+7$.

Explanation of the samples: Sample $1$: Because there is only one customer, no matter what happens, there cannot be two people ordering the same dish. Therefore, the required probability is $1$. Sample $2$: For each customer, the probability of ordering only dish $1$ is $\dfrac12$, the probability of ordering only dish $2$ is $\dfrac14$, and the probability of ordering both dishes is $\dfrac14$. For the two people to not order any common dish, one must order only dish $1$ and the other must order only dish $2$. The probability is $\dfrac14\times\dfrac12+\dfrac12\times\dfrac14=\dfrac14$, which modulo $10^9+7$ is $250000002$. ********* Hint: If you do not know how to take a rational number modulo, please see [P2613](https://www.luogu.com.cn/problem/P2613). ******** Constraints: For $10\%$ of the testdata, $k=1$. For another $10\%$ of the testdata, $1\le k\le n\le5$. For another $20\%$ of the testdata, $1\le k\le3$. For another $30\%$ of the testdata, $1\le k\le n\le10^3$. For all testdata, $1\le k\le n\le 10^8$. Translated by ChatGPT 5