Vào sinh nhật lần thứ mười ba của cậu, bố mẹ Donald đã mua cho cậu một bộ khối Lego hoàn toàn mới. Trong bộ này có ~n~ khối lập phương có kích thước bằng nhau, trong đó khối thứ ~i~ có màu ~i~. Sử dụng những hình khối này, cậu quyết định xây một bức tường.

Donald sẽ xây bức tường của mình trên một đế Lego có ~k~ vị trí có thể đặt các khối. Cậu ấy xếp các hình khối theo cách sau:

• Đầu tiên, cậu đặt khối lập phương có màu ~1~ vào một điểm tùy ý trên đế.
• Với mỗi khối từ ~2~ đến ~n~, cậu ta đặt nó ở vị trí kề với vị trí khối lập phương đã đặt trước đó. Nếu chỗ đó không trống, anh ta đặt khối mới lên trên tất cả các khối khác ở đó.

Sau khi xây bức tường, Donald viết lên một tờ giấy một dãy số có độ dài ~k~: ở vị trí thứ ~i~ trong dãy, cậu viết màu của hình lập phương trên cùng ở vị trí thứ ~i~, hoặc ~0~ nếu không có khối lập phương ở đó.

Cậu ta ngay lập tức tự hỏi mình có thể viết được tất cả bao nhiêu dãy số khác nhau trên mảnh giấy. Hai dãy được coi là khác nhau nếu tồn tại một vị trí mà chúng khác nhau. Sau một thời gian, cậu ấy đã tính toán được lời giải nhưng không chắc liệu nó có đúng hay không nên nhờ bạn giúp đỡ.

Input

Dòng duy nhất chứa hai số nguyên dương ~n~ và ~k~ (~2 \leq n, k \leq 5000~) mô tả số khối lập phương và số vị trí đặt của đế Lego.

Output

Đưa ra câu trả lời cho câu hỏi của Donald sau khi chia lấy dư cho ~10^9+7~.

Scoring

1. ~n, k \leq 18~ (20 điểm)

2. ~n, k \leq 50~ (30 điểm)

3. ~n, k \leq 500~ (30 điểm)

4. Không có ràng buộc gì thêm (30 điểm)

Sample Input 1

4 3

Sample Output 1

8

Sample Input 2

3 5

Sample Output 2

14

Sample Input 3

100 200

Sample Output 3

410783331

Explanation

• Ở ví dụ đầu tiên, các dãy số có thể tạo ra được là ~(0,3,4)~, ~(2,3,4)~, ~(0,4,3)~, ~(1,4,3)~, ~(4,3,0)~, ~(4,3,2)~, ~(3,4,0)~, ~(3,4,1)~.
• Ở ví dụ thứ hai, một trong số các dãy số đó là ~(0,3,2,0,0)~, thu được bằng cách đặt khối thứ nhất vào vị trí thứ ~2~, đặt khối thứ ~2~ ở vị trí thứ ~3~, và đặt khối thứ ~3~ ở vị trí thứ ~2~ (đặt trên khối thứ nhất).