Hệ thống camera xe buýt

Một chiếc xe buýt được trang bị hệ thống camera ghi lại sự thay đổi số hành khách sau mỗi trạm dừng.

Nếu $x$ là số hành khách trên xe ngay trước một trạm dừng và $y$ là số hành khách ngay sau trạm dừng đó, hệ thống ghi lại giá trị $y-x$.

Chuyến chạy thử được thực hiện với $n$ trạm dừng, hệ thống ghi lại dãy số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là giá trị ghi được tại trạm thứ $i$ (các trạm được đánh số từ $1$ đến $n$ theo thứ tự thời gian).

Xe buýt có sức chứa $w$, nghĩa là tại mọi thời điểm số hành khách trên xe phải nằm trong đoạn từ $0$ đến $w$ (kể cả thời điểm trước trạm dừng đầu tiên).

Hãy đếm số cách chọn số hành khách có trên xe trước trạm dừng đầu tiên sao cho không có mâu thuẫn nào xảy ra. Nếu không có cách nào, in ra $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $w$: số trạm dừng và sức chứa của xe.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách chọn số hành khách ban đầu.

Ràng buộc

• $1\le n\le 1000$
• $1\le w\le {10}^9$
• $-{10}^6\le a_i\le {10}^6$

Ví dụ