Đếm số dãy có độ dài \(n\) mà trong đó mỗi phần tử là một số nguyên từ \(1...k\) và mỗi số nguyên từ \(1...k\) xuất hiện ít nhất một lần trong dãy.

Ví dụ, khi \(n = 6\) và \(k = 4\), một số dãy hợp lệ là \([1,3,1,4,3,2]\) và \([2,2,1,3,4,2]\).

Input

• Một dòng duy nhất chứa 2 số nguyên \(n\) và \(k\).
• \(1 \leq k \leq n \leq 10^6\)

Output

• Một số nguyên duy nhất: số dãy có thể tạo được sau khi modulo cho \(10^9 + 7\).

Example

6 4

1560