Nhân dịp sinh nhật lần thứ mười ba của mình, DoMixi được fan tặng một hộp LEGO xịn! Trong hộp có ~n~ khối lego, khối thứ ~i~ có màu ~i~. DoMixi quyết định xây một bức tường trên một đế LEGO dạng hàng ngang có ~k~ vị trí đặt khối.

DoMixi xây tường theo quy tắc sau:

• Đầu tiên, đặt khối màu ~1~ vào một vị trí bất kỳ trên đế.
• Với mỗi khối từ ~2~ đến ~n~, đặt nó vào vị trí kề với khối vừa đặt. Nếu vị trí đó đã có khối, thì chồng khối mới lên trên tất cả các khối ở đó.

Sau khi xây xong, DoMixi ghi lên giấy một dãy độ dài ~k~: vị trí thứ ~i~ ghi màu của khối trên cùng ở vị trí đó, hoặc ~0~ nếu không có khối nào.

DoMixi tự hỏi: có bao nhiêu dãy khác nhau có thể xuất hiện? Hai dãy được coi là khác nhau nếu tồn tại ít nhất một vị trí mà hai dãy có giá trị khác nhau.

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên ~n~ và ~k~ (~2 \le n, k \le 5000~).

Kết quả

In ra số dãy khác nhau có thể xuất hiện, modulo ~10^9 + 7~.

Ví dụ

Đầu vào 1:

4 3

Đầu ra 1:

8

Đầu vào 2:

3 5

Đầu ra 2:

14

Đầu vào 3:

100 200

Đầu ra 3:

410783331

Giải thích ví dụ 1: Tất cả các dãy có thể 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)~.

Giới hạn