Khối lập phương

Time limit: 2.0s , Memory limit: 256M , Points: 1

Hình ảnh tạo bởi ChatGPT

Nhân dịp sinh nhật, Dona được bố mẹ tặng một bộ gồm $n$ ~n~ khối lập phương kích thước $1×1×1$ đầy màu sắc, mỗi khối có một màu sắc khác nhau, khối thứ $i$ ~i~ có màu $i$ ~i~. Trong bộ đồ chơi còn có một dải băng kích thước $1×k$ dùng để đặt các khối lập phương vào đó. Dải băng có thể đặt tối đa $k$ ~k~ khối lập phương, tuy nhiên Dona muốn nhiều hơn thế. Dona còn nghĩ ra cách đặt các khối chồng lên nhau, cụ thể cách đặt như sau:

Ban đầu, Dona lựa chọn một trong $k$ ~k~ vị trí để đặt khối lập phương đầu tiên vào.
Từ khối thứ $2$ ~2~ đến khối thứ $n$ ~n~, Dona đặt khối $i$ ~i~ tại vị trí ngay bên cạnh liền kề (trái hoặc phải) khối đã đặt trước đó (khối $i-1$ ~i-1~). Nếu hai bên trái hoặc phải của khối $i-1$ ~i-1~ đã được đặt, Dona sẽ đặt khối thứ $i$ ~i~ lên trên khối ở vị trí trái hoặc phải đó. Chú ý rằng không có giới hạn cho độ cao của việc xếp khối chồng lên nhau.

Sau khi đặt xong, Dona nhìn dải ma trận theo hướng từ trên xuống dưới theo góc nhìn thẳng đứng và thấy trên dải băng có rất nhiều màu sắc từ các khối lập phương. Dãy màu được biểu thị bởi các số nguyên là màu sắc của khối lập phương, nếu tại vị trí nào không đặt khối thì xem như mang màu $0$ ~0~. Dona muốn biết có tổng cộng bao nhiêu dải màu sắc khác nhau có thể tạo thành.

Input

Dòng duy nhất chứa hai số nguyên $n$ ~n~ và $k$ ~k~ $(1 \le n,k \le 5000)$ ~(1 \le n,k \le 5000)~ là số lượng khối lập phương và kích thước dải băng.

Output

In ra số lượng dải màu sắc khác nhau có thể tạo thành, kết quả chia lấy dư cho $10^9 + 7$ ~10^9 + 7~.

Samples

Sample Input 1

4 3

Sample Output 1

Sample Input 2

3 5

Sample Output 2

Sample Input 3

100 200

Sample Output 3

410783331

Scoring

Subtask $1$ ~1~ với $20\%$ ~20\%~ số điểm: $n,k \le 18$ ~n,k \le 18~
Subtask $2$ ~2~ với $22\%$ ~22\%~ số điểm: $n,k \le 50$ ~n,k \le 50~
Subtask $3$ ~3~ với $28\%$ ~28\%~ số điểm: $n,k \le 500$ ~n,k \le 500~
Subtask $4$ ~4~ với $30\%$ ~30\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Trong ví dụ đầu tiên, Dona có thể tạo thành các dãy màu $(0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1)$ .
Trong ví dụ thứ hai, Dona có thể tạo dãy màu $(0,3,2,0,0)$ ~(0,3,2,0,0)~ bằng cách đặt khối đầu tiên tại vị trí $2$ ~2~, đặt khối thứ hai tại vị trí $3$ ~3~ và đặt khối thứ ba tại vị trí $2$ ~2~ (đặt lên trên khối đầu tiên).