Giáo sư X sắp phải đi họp và ông chuẩn bị một bài tập làm văn cho sinh viên làm trong thời gian ông đi vắng. Giáo sư X có \(m\) tờ giấy thi để phát cho \(n\) sinh viên. Tùy theo trình độ viết dài, viết hỏng của từng người, ông xác định chính xác được rằng sinh viên thứ i phải được phát không ít hơn ai tờ giấy thi.

Yêu cầu : Đếm số cách phát \(m\) tờ giấy thi cho \(n\) sinh viên theo yêu cầu trên. Hai cách phát giấy thi được gọi là khác nhau nếu tồn tại một sinh viên nhận được số tờ giấy thi khác nhau trong hai cách đó.

Input

• Dòng 1 chứa hai số nguyên dương \(m \leq 10^9;n \leq 10^5\)
• Dòng 2 chứa 𝑛 số nguyên dương \(a_1,a_2,\ldots,a_n(∀i:ai \leq 10^9)\)

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

5 3 
1 1 2 

3