Дано масив з цілих чисел [a_1, a_2, \ldots, a_n]. За одну операцію можна зробити наступне:
Виберіть довільне від до . Після цього, замініть a_i на -(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
В першому прикладі, з ми можемо отримати лише , а з лише .
В другому прикладі, масив завжди міститиме лише нулі.