Абсолютно неадекватні операції#10766
Дано масив з цілих чисел [a_1, a_2, \ldots, a_n]. За одну операцію можна зробити наступне:
Вибрати деяке , для якого 2\le i \le n-1.
Нехай a_i = x. Тоді ми додаємо до a_{i-1} та a_{i+1}, а a_i замінюємо на .
Наприклад, якщо масив мав вигляд [1, 2, -1, 3], то ми можемо обрати i = 3, виконати операцію, і отримати масив [1, 1, 1, 2].
Ви можете застосовувати дану операцію до масиву довільну кількість разів. Скільки різних масивів ви можете отримати? Якщо ви можете отримати нескінченну кількість масивів, виведіть , інакше виведіть число цих масивів за модулем 10^9 + 7.
Два масиви вважаються різними, якщо вони відрізняються принаймні в одній позиції.
Перший рядок вхідних даних містить єдине ціле число (3 \le n \le 10^5) — довжину масиву.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — елементи масиву.
Якщо ви можете отримати нескінченну кількість масивів, виведіть , інакше виведіть число цих масивів за модулем 10^9 + 7.
Example 1
Example 2
Example 3
В першому прикладі, ми можемо застосувати операцію лише для i = 2, що дає два різні масиви: [18, 9, 2021] та [27, -9, 2030].
В другому прикладі, яку б операцію ми не застосували, масив лишатиметься рівним [0, 0, 0, 0, 0].