Có các loại ngoặc như (), {}, or []

Mỗi loại ngoặc được gán bằng một số nguyên

Một số nguyên âm -x biểu thị một ngoặc mở thuộc về kiểu ngoặc x

Trong khi một số nguyên dương x biểu thị một ngoặc đóng thuộc về x

Một dãy gồm các số nguyên như vậy được gọi là một dãy ngoặc

Một dãy ngoặc được gọi là cân bằng nếu các điều kiện sau thỏa mãn:

1. Dãy rỗng được gọi là một dãy ngoặc cân bằng

2. Nếu S là một dãy ngoặc cân bằng thì -xSx được gọi là một dãy  ngoặc cân bằng

3. Nếu S và T là dãy  ngoặc cân bằng, thì ST cũng được gọi là một dãy ngoặc cân bằng

Ví dụ, "-1 -2 2 -3 -4 4 3 1" là một dãy ngoặc cân bằng, nhưng "-1 -2 1 2" không phải

Cho một dãy ngoặc (có thể cân bằng hoặc không) gồm N số nguyên.

Có 2 mũ N cách để hình thành nên dãy con của dãy

Ta cần biết có bao nhiêu dãy con của dãy (dãy con của một dãy là một dãy thu được bằng cách xóa đi một số phần tử trong dãy) là cân bằng, đưa ra kết quả chia lấy dư cho 10^9 +7

Input

Dòng đầu tiên gồm N số nguyên biểu thị số ngoặc trong dãy

Dòng thứ hai gồm N số nguyên A₁, A₂, ..., A_N  biểu thị kiểu ngoặc.

Một số âm biểu thị ngoặc mở, một số dương biểu thị một ngoặc đóng

Output

Đưa ra câu trả lời trên một dòng

Giới hạn:

• 1 ≤ N ≤ 100
• -10⁹ ≤ A_i ≤ 10⁹
• A_i ≠ 0
• Không đảm bảo mỗi cặp ngoặc mở sẽ có một ngoặc đóng cùng kiểu và ngược lại

Subtasks

• Subtask N ≤ 10 Points: 10
• Subtask N ≤ 20 Points: 15
• Subtask N ≤ 100 Points: 75

Input:
11
-1 -2 9 2 -3 -4 3 4 8 8 1 

Output:
12