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:

1. Tổng số ghế của các đảng trong liên minh phải lớn hơn ~N/2~.

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

• 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, \dots, M_K~ là số ghế của từng đảng ~(1 \le M_i \le N)~, với tổng ~M_1 + M_2 + \dots + 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

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.

Scoring

Sample Input 1

18 5
7 2 3 4 2

Sample Output 1

4

Sample Input 2

6 6
1 1 1 1 1 1

Sample Output 2

15

Notes

Trong test ví dụ 1: Giả sử các đảng là ~1, 2, 3, 4, 5~ theo thứ tự. Các liên minh cầm quyền ổn định có thể là: ~\{1,3\}, \{1,4\}, \{1,2,5\}, \{2,3,4,5\}~. Nhóm ~\{1,2\}~ không phải liên minh cầm quyền vì chỉ có tổng ~9~ ghế, không lớn hơn ~N/2 = 9~. Nhóm ~\{1,2,3\}~ là liên minh cầm quyền không ổn định, vì khi loại ~2~ ra vẫn còn ~\{1,3\}~ có đủ số ghế lớn hơn ~N/2 = 9~.

Trong test ví dụ 2: Bất kỳ nhóm ~4~ đảng nào trong ~6~ đảng cũng tạo thành liên minh ổn định.