Dựng mảng

Ta xây dựng dãy số \(a_1, a_2, \dots, a_n\) theo các quy tắc sau:

• \(a_1\) là một số nguyên bất kỳ thuộc đoạn \([1, k]\).

• Với mỗi \(i\) từ \(2\) đến \(n\), giá trị \(a_i\) được chọn sao cho:

• \(a_i = a_{i-1} + 1\) hoặc \(a_i = a_{i-1} - 1\);

• và luôn đảm bảo \(1 \le a_i \le k\).

Sau khi xây dựng xong dãy \(a\), ta định nghĩa:

• \(lst(i) = j\) là vị trí \(j\) cuối cùng sao cho \(a[j]=i\).
• \(lst(i) = 0\) nếu không tồn tại vị trí \(j\) sao cho \(a[j]=i\).

Từ dãy \(a\), ta thu được một dãy mới gồm \(k\) phần tử là \((\text{lst}(1), \text{lst}(2), \dots, \text{lst}(k))\).

Vậy với bất kì dãy \(a\) có thể tạo ra, yêu cầu đếm xem có thể tạo được bao nhiêu dãy \(lst\) khác nhau.

Input

Gồm hai số nguyên \(n\) và \(k\) \((1 \le n, k \le 5000)\).

Output

In ra một số nguyên --- số lượng dãy \(lst\) khác nhau thu được, modulo \(10^9 + 7\).

Example

4 3

8

Scoring

• Subtask 1 (20 điểm): \(n, k \le 18\)
• Subtask 2 (30 điểm): \(n, k \le 50\)
• Subtask 3 (30 điểm): \(n, k \le 500\)
• Subtask 4 (20 điểm): Không có ràng buộc gì thêm.