Grading exams P40362

Professor Oak has graded n exams, and now he has to transfer the grades to some webpage. He has not sorted the exams at all, so he has a pile of n randomly permuted exams, which he will take one by one. In the screen, there is only space for ℓ ‍lines at a time (with 2ℓ ≥ n), each one corresponding to one student. Initially, the webpage shows the alphabetically first ℓ students. When the name of the next student is not among the ℓ visible lines, Prof. Oak will have to press the End key or the Home key before being able to introduce the grade.

For instance, suppose n = 6, ℓ = 4, and that the names of the students correspond to the permutation 4 2 6 3 5 1. Initially, the screen will show the lines 1, 2, 3 and 4. Prof. Oak will directly introduce the grades of 4 and 2, press the End key (therefore, he will see the lines 3, 4, 5 and 6), introduce the grades of 6, 3 and 5, press the Home key, and introduce the grade of 1. In this example, the cost is 2. For the permutation 1 2 3 4 5 6 the cost is just 1, and for the permutation 6 1 5 2 4 3 it is 4.

Given n and ℓ, can you compute c(n, ℓ), the expected number of times that Prof. Oak will have to press the End and the Home keys while transferring all the grades? For instance, c(2, 1) = 1.5, because the permutation 1 2 has cost 1 and the permutation 2 1 has cost 2.

Input

Input consists of several cases, with n and ℓ. Assume 2 ≤ n ≤ 10⁵, 2ℓ ≥ n and ℓ ≤ n.

Output

For every case, print ( n!   c(n, ℓ) ) modulo P = 10⁹ + 7. Note that we multiply by n! to get rid of decimals, and we make the computations modulo P to avoid overflows.