Liên minh

Tại một quốc gia XYZ, trong quốc hội có \(N\) ghế, mỗi ghế thuộc về một trong \(K\) đảng. Nhiệm vụ của các đảng là thành lập một liên minh cầm quyền.

Để một liên minh có thể cầm quyền, liên minh cần chiếm đa số trong quốc hội. Tuy nhiên, số lượng đảng trong liên minh càng nhiều thì sự ổn định càng giảm do sự khác biệt quan điểm. Do đó, một liên minh mà sau khi loại bỏ bất kỳ đảng nào vẫn còn chiếm đa số thì không được xem là ổn định.

Cụ thể, một nhóm các đảng có thể tạo thành liên minh cầm quyền ổn định nếu thỏa mãn hai điều kiện:

• Tổng số ghế của các đảng trong liên minh phải lớn hơn \(N/2\).
• Nếu loại bỏ bất kỳ đảng nào khỏi liên minh thì số ghế còn lại không còn lớn hơn \(N/2\).

Yêu cầu: Hãy đếm số lượng nhóm đảng có thể tạo thành liên minh cầm quyền ổn định.

Input

Vào từ tệp văn bản SPC.INP:

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(K\), theo thứ tự là số ghế trong quốc hội và số đảng \((1 \le N \le 10^{18},\ 1 \le K \le 36)\);
• Dòng thứ hai gồm \(K\) số nguyên \(M_1, M_2, \ldots, M_K\) là số ghế của từng đảng \((1 \le M_i \le N)\), với tổng \(M_1 + M_2 + \ldots + M_K = N\).

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra tệp văn bản SPC.OUT một số nguyên duy nhất là số lượng liên minh cầm quyền ổn định có thể tạo thành.

Example

18 5
7 2 3 4 2

4

6 6
1 1 1 1 1 1

15

Scoring

• Subtask 1 (20% số điểm): \(K = 3\);
• Subtask 2 (20% số điểm): \(K = N\);
• Subtask 3 (15% số điểm): \(K \le 20\);
• Subtask 4 (15% số điểm): \(N \le 10^6\);
• Subtask 5 (30% số điểm): không có ràng buộc gì thêm.