Castle Room Reassignment

Saruka owns a huge castle with n rooms. Each room is labeled with a number p_i (1 ≤ i ≤ n). Initially, the mapping p can be arbitrary. One day, Saruka invites his companions LYL and MagHSK to play. They agree on the following rule: if a person is currently in room i, in the next step he moves to room p_i, and in the step after that he goes to room p_pi and so on.

To make the game more interesting, Saruka decides to rewrite the numbers on the rooms (i.e. reassign p_i for all 1 ≤ i ≤ n) so that the following conditions are satisfied:

• For every room with index i from 1 to k (inclusive), when starting from room i and moving repeatedly using the rule, one must eventually visit room 1. In particular, even if one starts at room 1, after at least one move room 1 should be reached again (thus if p₁ = 1, that is acceptable).
• For every room with index greater than k, if one starts in that room and follows the rule, room 1 must never be reached.

In other words, if we define the basin of attraction of room 1 as the set of rooms that eventually lead to room 1 via the mapping, then this basin must be exactly the set {1, 2, ..., k}.

Your task is to compute the number of ways to assign numbers p₁, p₂, ..., p_n (each in the range 1 through n) such that the above conditions hold. As the answer can be huge, output it modulo \(10^9+7\).

Hint (in terms of combinatorics): The functional graph on the first k nodes must consist of a unique cycle containing room 1 (which could be a 1-cycle) together with trees attached to the nodes on the cycle. The number of valid assignments for nodes 1..k can be computed by summing over possible cycle lengths. Meanwhile, for the remaining rooms, the function must map them to rooms outside {1, 2, ..., k}.

inputFormat

The input consists of a single line containing two space-separated integers \(n\) and \(k\) (with 1 ≤ k ≤ n):

n k

Here, \(n\) is the total number of rooms, and \(k\) is the number of rooms whose trajectories must eventually reach room 1.

outputFormat

Output a single integer: the number of valid assignments of p_i for rooms 1 to \(n\) modulo \(10^9+7\).

sample

3 1

4