eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

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

Дано масив з $n$ цілих чисел $[a_1, a_2, \ldots, a_n]$. За одну операцію можна зробити наступне: \begin{itemize} \item Вибрати деяке $i$, для якого $2\le i \le n-1$. \item Нехай $a_i = x$. Тоді ми додаємо $x$ до $a_{i-1}$ та $a_{i+1}$, а $a_i$ замінюємо на $-x$. \end{itemize} Наприклад, якщо масив мав вигляд $[1, 2, -1, 3]$, то ми можемо обрати $i = 3$, виконати операцію, і отримати масив $[1, 1, 1, 2]$. Ви можете застосовувати дану операцію до масиву довільну кількість разів. Скільки різних масивів ви можете отримати? Якщо ви можете отримати нескінченну кількість масивів, виведіть $-1$, інакше виведіть число цих масивів за модулем $10^9 + 7$. Два масиви вважаються різними, якщо вони відрізняються принаймні в одній позиції. \InputFile Перший рядок вхідних даних містить єдине ціле число $n$ ($3 \le n \le 10^5$) --- довжину масиву. Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) --- елементи масиву. \OutputFile Якщо ви можете отримати нескінченну кількість масивів, виведіть $-1$, інакше виведіть число цих масивів за модулем $10^9 + 7$. \Note В першому прикладі, ми можемо застосувати операцію лише для $i = 2$, що дає два різні масиви: $[18, 9, 2021]$ та $[27, -9, 2030]$. В другому прикладі, яку б операцію ми не застосували, масив лишатиметься рівним $[0, 0, 0, 0, 0]$.
Time limit 1 second
Memory limit 256 MiB
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
Author Anton Trygub