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

Дано масив з $n$ цілих чисел $[a_1,a_2,\dots ,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$.

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

Входные данные

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

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

Выходные данные

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

Примеры

Примечание

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

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