Ngày mai là lễ Giáng Sinh, Tấm muốn đi đến buổi dạ tiệc cùng hoàng tử, nhưng mụ dì ghẻ lại bắt nàng phải ở nhà làm việc. Tuy vậy, mụ ta vẫn rất sợ hoàng tử sẽ trách tội nên đã ra một câu đố cho Tấm, nếu nàng giải được thì sẽ được miễn việc nhà và lập tức có thể chuẩn bị diện đầm đi dạ hội.

Câu đố như sau: Mụ đặt \(n\) chiếc bát nằm liên tiếp nhau thành một đường thẳng và đưa cho Tấm một rổ có \(m\) hạt đậu. Yêu cầu Tấm đếm số cách bỏ tất cả \(m\) hạt đậu vào \(n\) chiếc bát sao cho mỗi chiếc bát chỉ chứa tối đa \(1\) hạt đậu, và không được có hai chiếc bát nào cạnh nhau đều chứa đậu.

Vì không được ăn học tử tế nên câu hỏi này quá hóc búa với Tấm. Nàng khóc lóc chờ Bụt hiện ra giúp, nhưng buồn thay Bụt cũng đang bận ở nhà trang trí cây Thông cho đêm Noel mất rồi. Tấm đau đớn, tấm gục ngã nhưng không biết làm gì hơn :(

Bằng tài trí của mình, các bạn IT NBK hãy giúp Tấm giải câu đố này để nàng được đến bên hoàng tử nhé! Vì kết quả bài toán có thể rất lớn nên chỉ cần tính và in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n\) và \(m\).

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Ví dụ

Sample input

6 3

Sample output

4

Ràng buộc

• Subtask 1 (30%): \(1\leq n,\ m\leq20\);
• Subtask 2 (70%): \(1\leq n\leq10^9,\ 1\leq m\leq10^5\).