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ám 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).

Yêu cầu: Cho \(n\) và \(k\), 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 chứa hai số nguyên dương \(n,k\).

Output

• 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\)).

Scoring

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

Example

10 3

4