You are given \(N\) boxes that are kept in a straight line. You are also given \(M\) colors such that (\(M\le N\)). You cannot change the position of boxes. Determine the number of ways to color the boxes such that if you select any \(M\) consecutive boxes then the color of each box is unique.

Since the number could be large, print the answer modulo \(10^9+7\).

Input format

Two space-separated integers \(N\) and \(M\)

Output format

For the provided inputs, print the required answer.

Constraints

\(1 \le M \le N \le10^6\)