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ó 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.

Dữ liệu vào: Đọc từ tệp TIENHOA.INP gồm một dòng duy nhất chứa hai số nguyên n và k (1 ≤ n ≤ 10^3, 1 ≤ k ≤ 10^5).

Dữ liệu ra: Ghi ra tệp TIENHOA.OUT 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 (đã chia lấy dư cho 10^9 + 7).

Ví dụ:

Input:

5 3

Output:

65

Ràng buộc:

● 40% số điểm tương ứng với n ≤ 100, k ≤ 10^3.

● 60% số điểm còn lại không có ràng buộc gì thêm.