Nhảy lò cò là một trò chơi dân gian Việt Nam. Thuở bé Lan rất thích chơi trò này. Vì vậy, khi được học môn "Phân tích và thiết kế thuật toán", Lan đã đặt ra một bài toán khá thú vị liên quan tới trò chơi này. Trên mặt phẳng vẽ ~n~ vòng tròn. Các vòng tròn này lại được xếp trên một vòng tròn lớn và được đánh số từ từ ~1~ đến ~n~ theo chiều đi vòng quanh vòng tròn lớn thuận chiều kim đồng hồ. Hai vòng tròn nhỏ liên tiếp nhau theo một chiều đi vòng quanh vòng tròn lớn được gọi là ở bên cạnh nhau.

Người chơi bắt đầu từ vòng tròn đánh số ~1~, mỗi bước nhảy người chơi sẽ di chuyển sang một trong hai vòng tròn bên cạnh. Hãy giúp Lan giải quyết bài toán sau: Đếm xem có bao nhiêu cách khác nhau thực hiện ~k~ bước nhảy bắt đầu từ vòng tròn ~1~ rồi lại quay về vòng tròn ~1~.

Input

Một dòng chứa hai số nguyên dương ~n~ và ~k~ (~3\le n\le 4000, 1\le k \le 10^6~) — số lượng vòng tròn và số lượng bước nhảy.

Output

Một số nguyên là phần dư trong phép chia số lượng cách nhảy tìm được cho ~10^9+7~.

Scoring

Sample Input 1

3 2

Sample Output 1

2