Có \(n\) vật và \(k\) màu. Tô mỗi vật một màu. Biết rằng mỗi màu có thể tô tối đa \(lim_i\) vật. Đếm số cách tô màu modulo \(10^9+7\).

Định dạng đầu vào

• Dòng đầu: \(n, k\) (\(1 \le k \le 10\), \(1 \le n \le 10^5\)).
• Dòng hai: \(k\) số \(lim_1, \dots, lim_k\) (\(0 \le lim_i \le n\)).

Định dạng đầu ra

• Một số nguyên là kết quả.

Ví dụ

Input:

5 2
3 2

Output:

10

Ràng buộc

• 100% số điểm: \(k \le 10\).