Bạn được cho hai số nguyên \(n\) và \(k\).

Yêu cầu: Hãy in ra số tập con khác nhau gồm \(k\) phần tử (có thể lặp) trong các số nguyên từ \(1\) đến \(n\).

Hai tập con được xem là khác nhau khi sắp xếp hai tập lại, tồn tại một vị trí mà phần tử ở vị trí đó trong hai tập là khác nhau.

Ví dụ: \((1, 2)\), \((2, 2)\) là tập con thỏa mãn. \((1, 2)\) và \((2, 1)\) là hai tập con giống nhau.

Input

• Chứa số hai số nguyên \(n\) và \(k\) \((1 \le n, k \le 10^9)\).

Output

• Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Example

6 2 

21