Đế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ứ 2 số nguyên \(n\) và \(k\).

Output

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

Constraints

• \(1\leq k \leq n \leq 10^6\)

Example

Sample Input

6 4

Sample Output

1560