Hội thi Tin học trẻ được tổ chức hàng năm và đã thu hút được sự quan tâm của cả nước. Đề thi ngày càng phong phú và đa dạng là do sự đóng góp ý tưởng từ rất nhiều nhà khoa học và các tổ chức công nghệ. Đến nay, ngân hàng đề thi có tổng cộng \(n\) bài, các bài được đánh số từ \(1\) tới \(n\), bài thứ \(i\) có độ khó là \(i\). Để xây dựng đề thi năm nay, Ban giáo khảo muốn chọn \(k\) bài khác nhau từ ngân hàng đề thi mà tổng độ khó của \(k\) bài đúng bằng \(n\). Để khảo sát tính đa dạng của đề thi, Ban giám khảo muốn tính số cách xây dựng đề thi khác nhau (hai đề thi được gọi là khác nhau nếu có một bài được chọn trong đề thứ nhất nhưng không được chọn trong đề thứ hai).

Hãy giúp Ban giám khảo tính số cách xây dựng đề thi khác nhau. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Input

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

Output

• Ghi ra một số nguyên duy nhất là số dư của phép chia kết quả tìm được cho \((10^9 + 7)\).

Example

10 3

4

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\) và \(k \le 5\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6\) và \(k \le 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 2\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k = 3\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^9\) và \(k \le 5\).