Phản Vật Chất

Cho dãy $N$ số nguyên dương $a_1,a_2,\dots ,a_N$. Với mỗi phần tử ta có thể chọn dấu cộng $(+a_i)$ hoặc dấu trừ $(-a_i)$.

Hãy đếm số cách chọn một đoạn con liên tiếp $a_l,a_{l+1},\dots ,a_r$ ($1\le l\le r\le N$) cùng với một cách gán dấu cho từng phần tử của đoạn sao cho tổng có dấu bằng $0$.

Hai cách được coi là khác nhau nếu chúng có đoạn $[l,r]$ khác nhau, hoặc tồn tại ít nhất một vị trí trong đoạn được gán dấu khác nhau.

In kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$.

Dữ liệu ra

• Một số nguyên duy nhất là số cách đếm được, lấy dư cho ${10}^9+7$.

Ràng buộc

• $1\le N\le 1000$
• $1\le a_i\le 1000$
• $a_1+a_2+\cdots +a_N\le 10000$

Ví dụ