405834: GYM102133 E The secret of betting

Hi! I'm a hardcore sports fan. Watching your favorite sports team win is an exciting moment. And it can be not only joyful, but profitable, if you know how to win bets with bookmakers. But how to predict who will win the match? That is the question…

But I’ve finally revealed the secret. All the players have all the different numbers from 1 to n on their shirts. The trick is to know a special order of n players standing during the national anthem. If |A_i - i| ≤ k for any i in range [1, n], then the game will end in victory for your favorite team. Out of kindness, the referee will tell you the number k before the match starts.

For example, k = 1 and the order of the players is (3, 4, 1, 2). Your team will definitely lose under the circumstances. But if k = 2, they will definitely win.

I have already made enough money from bookmakers, so now it’s your turn to use this trick. Count the number of winning permutations of n players for a given k.

The first line contains two integers n (a number of players on a team) and k (a secret parameter you were told).

You are required to output a number of winning permutations modulo 10⁹ + 7.

4 2

14