Cho hai số nguyên dương ~m~ và ~n~. Xét phương trình bậc nhất ~n~ ẩn:

$$ x_{1}+x_{2}+x_{3}+\cdots+x_{n}=m $$

với ~n~ điều kiện ràng buộc ~x_{i} \geq a_{i}, a_{i}~ nguyên dương ~(i=1,2, . . n)~.

Gọi ~T~ là số các nghiệm nguyên của phương trình thỏa mãn các điều kiện ràng buộc. Hãy tìm số dư khi chia ~T~ cho ~1000000007~.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương ~m~ và ~n\left(m \leq 10^{9}, n \leq 10^{5}\right)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, \ldots, a_{n}\left(a_{i} \leq 10^{9}\right)~.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả:

• Ghi ra trên một dòng, một số nguyên duy nhất là kết quả theo yêu cầu của bài toán.

Ví dụ:

Sample Input

7 3 
2 2 1

Sample Output

6

Giải thích:

Có ~6~ nghiệm là ~(2 ; 2 ; 3),(2 ; 3 ; 2),(2 ; 4 ; 1),(3 ; 2 ; 2),(3 ; 3 ; 1),(4 ; 2 ; 1)~.

Ràng buộc:

• Có ~30 \%~ số test ứng với ~30 \%~ số điểm của bài có ~m \leq 1000, n \leq 3~.
• Có ~40 \%~ số test khác ứng với ~40 \%~ số điểm của bài có ~m \leq 1000, n \leq 1000~.
• Có ~30 \%~ số test còn lại ứng với ~30 \%~ số điểm của bài có ~m \leq 10^{9}, n \leq 10^{5}~.