Đếm số ánh xạ từ tập \(n\) phần tử lên (onto) tập \(k\) phần tử, modulo \(10^9+7\). Mỗi phần tử trong tập đích phải được ánh xạ tới ít nhất một lần.

Định dạng đầu vào

• Một dòng chứa \(n, k\) (\(1 \le k \le n \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là kết quả modulo \(10^9+7\).

Ví dụ

Input:

4 3

Output:

36

Ràng buộc

• 100% số điểm: \(n \le 10^6\).