Мінус сума#12872

Мінус сума

1 секунда
256 мегабайтів
Складна

Дано масив з цілих чисел [a_1, a_2, \ldots, a_n]. За одну операцію можна зробити наступне:

Ви можете застосовувати дану операцію до масиву довільну кількість разів. Скільки різних масивів ви можете отримати? Якщо ви можете отримати нескінченну кількість масивів, виведіть , інакше виведіть число цих масивів по модулю .

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

Вхідні дані

Перший рядок містить єдине ціле число (1 \le t \le 10^4)  — кількість наборів вхідних даних. Далі слідує опис наборів вхідних даних.

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

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

Гарантується, що сума по всім наборам вхідних даних не перевищує 2\cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних, якщо ви можете отримати нескінченну кількість масивів, виведіть , інакше виведіть число цих масивів по модулю .

Приклади

Приклад 1

Loading
Loading

Примітка

В першому прикладі, з ми можемо отримати лише , а з лише .

В другому прикладі, масив завжди міститиме лише нулі.