Chỉ năm nay nữa thôi là sherry sẽ tốt nghiệp Đại Học rồi vì thế sherry muốn sinh nhật năm nay của mình sẽ thật ý nghĩa. Và Sherry mời tất cả bạn của mình đến dự sinh nhật ^^

Sherry tổ chức 1 trò chơi nhỏ cho tất cả các bạn cùng tham gia, sherry có 1 tờ giấy HCN kích thước 1 x N và M mảnh nhỏ hơn, mảnh giấy thứ i có kích thước 1 x A_i. Nây giờ sherry đố các bạn của mình có bao nhiêu cách đặt các mảnh giấy nhỏ theo thứ tự từ 1 đến M vào mảnh giấy 1 x N sao cho mỗi mảnh giấy cách nhau ít nhất 1 ô vuông (Nếu i < j thì mảnh giấy thứ i sẽ được đặt nằm trước mảnh giấy thứ j). Sherry hứa sẽ tặng 1 món quà đặc biệt cho bạn nào trả lời nhanh nhất :D

Dữ liệu vào:

Dòng 1: N, M ( 1 <= N <= 1000, 1 <= M <= N/2 )
Dòng 2: Gồm M số, số thứ i là A_i

Kết quả

Gồm 1 dòng duy nhất là số cách tìm được