Дано масив з n цілих чисел [a1,a2,…,an]. За одну операцію можна зробити наступне:
Вибрати деяке i, для якого 2≤i≤n−1.
Нехай ai=x. Тоді ми додаємо x до ai−1 та ai+1, а ai замінюємо на −x.
Наприклад, якщо масив мав вигляд [1,2,−1,3], то ми можемо обрати i=3, виконати операцію, і отримати масив [1,1,1,2].
Ви можете застосовувати дану операцію до масиву довільну кількість разів. Скільки різних масивів ви можете отримати? Якщо ви можете отримати нескінченну кількість масивів, виведіть −1, інакше виведіть число цих масивів за модулем 109+7.
Два масиви вважаються різними, якщо вони відрізняються принаймні в одній позиції.
Перший рядок вхідних даних містить єдине ціле число n (3≤n≤105) — довжину масиву.
Другий рядок містить n цілих чисел a1,a2,…,an (−109≤ai≤109) — елементи масиву.
Якщо ви можете отримати нескінченну кількість масивів, виведіть −1, інакше виведіть число цих масивів за модулем 109+7.
В першому прикладі, ми можемо застосувати операцію лише для i=2, що дає два різні масиви: [18,9,2021] та [27,−9,2030].
В другому прикладі, яку б операцію ми не застосували, масив лишатиметься рівним [0,0,0,0,0].