Bí ẩn tại H3.2

Ở một góc nào đó của câu lạc bộ H3.2, người ta truyền tai nhau về một chú chuột bí ẩn tên là PeterL. Không ai biết Peter trông như thế nào, sống ở đâu, thậm chí chưa từng có ai thật sự nhìn thấy PeterL. Thứ duy nhất khiến mọi người tin rằng Peter tồn tại là việc những món ăn được để lại trong câu lạc bộ đôi khi biến mất không một dấu vết.

Một ngày nọ, một chiếc bánh được đặt trên bàn tại H3.2. Chỉ vài phút sau, chiếc bánh biến mất. Không ai bước vào phòng, không ai chạm vào chiếc bánh. Tại nơi chiếc bánh từng nằm, mọi người phát hiện n dấu vết được sắp xếp theo thứ tự, dấu vết thứ i có giá trị năng lượng a_i.

Theo truyền thuyết, PeterL có thể chọn một dãy chỉ số: ~1 \le i_1 < i_2 < \dots < i_k \le n~

và tính tổng xen kẽ: ~a_{i_1}-a_{i_2}+a_{i_3}-a_{i_4}+\dots~

Nói cách khác, với dãy ~b_1,b_2,...,b_k~, tổng xen kẽ là: $$ \sum_{j=1}^{k}(-1)^{j+1}b_j $$

Bạn được cho một mảng không giảm a gồm n phần tử. Với mọi i, a_i=-1 hoặc a_i là một số nguyên dương.

Hãy tính số cách chọn các chỉ số: ~1 \le i_1 < i_2 < \dots < i_k \le n~

sao cho: ~a_{i_1}-a_{i_2}+a_{i_3}-a_{i_4}+\dots=0~

Hai cách chọn được xem là khác nhau nếu số lượng chỉ số khác nhau hoặc có ít nhất một vị trí được chọn khác nhau. Hai dãy con có cùng giá trị nhưng chọn từ các vị trí khác nhau vẫn được tính là hai cách khác nhau.

Dãy con rỗng cũng được xem là có tổng xen kẽ bằng 0.

Input

Dòng đầu tiên chứa số nguyên n (~1 \le n \le 2\cdot10^5~).

Dòng thứ hai chứa n số nguyên ~a_1,a_2,...,a_n~, với mỗi ~a_i=-1~ hoặc ~1\le a_i\le10^9~.

Mảng a được đảm bảo không giảm:

~a_1\le a_2\le\dots\le a_n~

Output

In ra số cách chọn dãy con có tổng xen kẽ bằng 0, modulo ~10^9+7~.

Kiến thức cần biết: Modulo

Trong bài toán đếm, số lượng đáp án có thể rất lớn. Vì vậy thay vì in trực tiếp đáp án, ta chỉ cần in phần dư của đáp án khi chia cho ~10^9+7~.

Với hai số nguyên a và m, ký hiệu: ~a \bmod m~ là phần dư khi chia a cho m.

Ví dụ:

• ~17 \bmod 5 = 2~
• ~100 \bmod 7 = 2~
• ~(10^9+8) \bmod (10^9+7)=1~

Khi tính toán, ta có thể lấy modulo sau mỗi phép cộng hoặc nhân:

~(a+b)\bmod m=((a\bmod m)+(b\bmod m))\bmod m~

~(a\cdot b)\bmod m=((a\bmod m)\cdot(b\bmod m))\bmod m~

Example

Input

5
-1 1 1 2 3

Output

6

Giải thích

Với a=[-1,1,1,2,3], có 6 cách chọn:

1. []
2. Chọn 2,3: [1,1], có 1-1=0.
3. Chọn 1,2,4: [-1,1,2], có -1-1+2=0.
4. Chọn 1,3,4: [-1,1,2].
5. Chọn 1,4,5: [-1,2,3], có -1-2+3=0.
6. Chọn toàn bộ mảng: [-1,1,1,2,3], có -1-1+1-2+3=0.

Vì vậy đáp án là 6.

Subtasks