Абсолютно неадекватні операції
Абсолютно неадекватні операції
Дано масив з 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
3 18 9 2021
2
5 0 0 0 0 0
1
6 1 -1 1 -1 1 -1
10
Note
В першому прикладі, ми можемо застосувати операцію лише для i = 2, що дає два різні масиви: [18, 9, 2021] та [27, -9, 2030].
В другому прикладі, яку б операцію ми не застосували, масив лишатиметься рівним [0, 0, 0, 0, 0].