K. K Happy Computers
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jose is a big computer fan, he likes them so much that he plans on buying one every week! However, due to the space in his house, he can only have $$$k$$$ computers at the same time, so whenever he buys one that won't fit, he sells the oldest one first.

Jose also likes to keep his computers happy, so he assigns them a name the computer chooses. The computers, being computers, always choose uniformly a random integer between $$$1$$$ and $$$N$$$ (because that's how Jose sets their configuration). However, a computer won't be happy if there is another computer in the house with its same name.

Jose was recently robbed and doesn't have any computers. Help him find the expected value of weeks that will pass before a computer is sad. It can be proven that the answer can be represented as a rational number $$$\frac{p}{q}$$$ with coprime $$$p$$$ and $$$q$$$. You need to output $$$p \cdot q^{-1}$$$ mod $$$10^{9}+7$$$.

Input

The first line of input contains two integers $$$N$$$ and $$$k$$$ ($$$1\leq N \leq 10^{12}$$$, $$$2\leq k\leq 10^{6}$$$) — The range of numbers that can be used to assign the name of a computer and the maximum number of computers that Jose can have at the same time, respectively.

Output

Print a single line — The answer to the problem modulo $$$10^9+7$$$.

Examples
Input
2 2
Output
3
Input
5 3
Output
4
Input
1000000000000 1000000
Output
798779352