Задачі
Абсолютно неадекватні операції
Абсолютно неадекватні операції
Дано масив з $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]$.
Вхідні дані #1
3 18 9 2021
Вихідні дані #1
2
Вхідні дані #2
5 0 0 0 0 0
Вихідні дані #2
1
Вхідні дані #3
6 1 -1 1 -1 1 -1
Вихідні дані #3
10