eolymp
bolt
Try our new interface for solving problems
Problems

Абсолютно неадекватні операції

Абсолютно неадекватні операції

Time limit 1 second
Memory limit 256 MiB

Дано масив з n цілих чисел [a_1, a_2, \ldots, a_n]. За одну операцію можна зробити наступне:

  • Вибрати деяке i, для якого 2\le i \le n-1.

  • Нехай a_i = x. Тоді ми додаємо x до a_{i-1} та a_{i+1}, а a_i замінюємо на -x.

Наприклад, якщо масив мав вигляд [1, 2, -1, 3], то ми можемо обрати i = 3, виконати операцію, і отримати масив [1, 1, 1, 2].

Ви можете застосовувати дану операцію до масиву довільну кількість разів. Скільки різних масивів ви можете отримати? Якщо ви можете отримати нескінченну кількість масивів, виведіть -1, інакше виведіть число цих масивів за модулем 10^9 + 7.

Два масиви вважаються різними, якщо вони відрізняються принаймні в одній позиції.

Input data

Перший рядок вхідних даних містить єдине ціле число n (3 \le n \le 10^5) — довжину масиву.

Другий рядок містить n цілих чисел a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — елементи масиву.

Output data

Якщо ви можете отримати нескінченну кількість масивів, виведіть -1, інакше виведіть число цих масивів за модулем 10^9 + 7.

Examples

Input example #1
3
18 9 2021
Output example #1
2
Input example #2
5
0 0 0 0 0
Output example #2
1
Input example #3
6
1 -1 1 -1 1 -1
Output example #3
10

Note

В першому прикладі, ми можемо застосувати операцію лише для i = 2, що дає два різні масиви: [18, 9, 2021] та [27, -9, 2030].

В другому прикладі, яку б операцію ми не застосували, масив лишатиметься рівним [0, 0, 0, 0, 0].

Author Anton Trygub