Trong một phòng thí nghiệm, các nhà khoa học xây dựng một hệ sinh thái gồm nhiều thực thể trí tuệ nhân tạo. Mỗi thực thể được gán một cấp độ năng lực là một số nguyên dương. Tại thời điểm ban đầu (ngày \(0\)) hệ sinh thái có \(n\) thực thể và tất cả đều ở cấp độ \(1\). Quá trình tiến hóa của hệ sinh thái diễn ra trong \(k\) ngày, ở mỗi ngày các thực thể đang tồn tại thực hiện lần lượt hai bước sau:

• Thứ nhất, mỗi thực thể đang ở cấp độ \(i\) tạo ra đúng \(i\) thực thể mới có cấp độ \(1\). Các thực thể mới được tạo ra trong ngày này chỉ bắt đầu tham gia quá trình tiến hóa từ ngày kế tiếp.
• Thứ hai, sau khi quá trình tạo mới kết thúc mỗi thực thể đã tồn tại từ đầu ngày sẽ tăng cấp từ \(i\) lên \(i + 1\).

Yêu cầu: Hãy xác định sau đúng \(k\) ngày hệ sinh thái có tổng cộng bao nhiêu thực thể. Vì kết quả có thể rất lớn hãy in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(k\) (\(1 \le n \le 10^3, 1 \le k \le 10^5\)).

Output

• Ghi ra một số nguyên duy nhất là số lượng thực thể có trong hệ sinh thái sau đúng \(k\) ngày lấy dư cho \(10^9 + 7\).

Example

5 3

65

Scoring

• \(40\%\) số điểm tương ứng với \(n \le 100, k \le 10^3\).
• \(60\%\) số điểm còn lại không ràng buộc gì thêm.