Tiết mục "Nhảy dân vũ" trong Lễ hội văn hóa dân gian năm nay có \(n\) lớp học tham gia, mỗi lớp đăng ký biểu diễn một tiết mục. Danh sách các tiết mục nhà trường cho phép đăng ký bao gồm \(k\) bài hát khác nhau (ví dụ như: Việt Nam ơi, Trống cơm, Con cào cào, …). Mỗi lớp có thể lựa chọn đăng ký một trong \(k\) bài hát này để biểu diễn. Đánh số thứ tự các bài hát này từ \(1\) tới \(k\). Bài hát thứ \(i\) được \(a_i\) lớp đăng ký.

Ban tổ chức muốn sắp xếp thứ tự biểu diễn của \(n\) tiết mục này để tạo thành một chương trình liên tục. Nhằm đánh giá độ đa dạng của chương trình, Ban tổ chức cần tính số lượng cách sắp xếp khác nhau của các tiết mục. Hai cách sắp xếp được coi là khác nhau nếu tồn tại ít nhất một vị trí \(i\) (\(1 \le i \le n\)) mà tiết mục (bài hát) tại thứ tự \(i\) trong hai cách sắp xếp là khác nhau.

Yêu cầu: Đếm số cách sắp xếp khác nhau (độ đa dạng), chia lấy dư cho \(10^9 + 7\).

Input

• Dọc vào từ tệp DANCE.INP:
  • Dòng đầu tiên gồm hai số nguyên dương \(n, k\) (\(1 \le k \le n \le 10^5\)).
  • Dòng thứ hai chứa \(k\) số nguyên dương \(a_1, a_2, \dots, a_k\) (\(1 \le a_i \le k\)).
  • Dữ liệu đầu vào đảm bảo \(a_1 + a_2 + \dots + a_k = n\).

Output

• Ghi ra tệp DANCE.OUT:
  • Một số nguyên duy nhất là độ đa dạng của chương trình, chia lấy dư \(10^9 + 7\).

Example

4 2
2 2

6

Ràng buộc

• \(30\%\) số điểm tương ứng với \(n \le 8\).
• \(30\%\) số điểm khác tương ứng \(k = 2, a_1 = 2\).
• \(20\%\) số điểm khác tương ứng với \(k = 2, n \le 10^3\).
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.