Chef has a sequence $A$ of $N$ integers such that $|A_{i}| ≤ 1$.

For each $x$ such that $-N ≤ x ≤ N$, find the number of non-empty subsequences of $A$ whose sum of elements is $x$. Since that answer may be too large, print this modulo $163,577,857$.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output: ------
Output $2N+1$ space-separated integers $C_{0}, C_{1} \ldots C_{2*N}$, where $C_{i}$ denotes the number of non-empty subsequences with sum $(i-N)$, modulo $163,577,857$.

------ Constraints: ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$|A_{i}| ≤ 1$ for each valid $i$
It's guaranteed that the total length of the arrays in one test file doesn't exceed $2*10^{6}$

------ Sample Input: ------

2
2
1 0
3
-1 1 -1

------ Sample Output: ------

0 0 1 2 0
0 1 3 2 1 0 0

------  Explanation: ------
In the first test case, the non-empty subsequences with sum $0$ are $\{0\}$ while the subsequences with sum $1$ are $\{1\}$ and $\{1,0\}$.

Source: codechef | Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Combinatorics

Mathematics


Solutions:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict
input = sys.stdin.readline
write = sys.stdout.write

def read_int() -> int:
	return int(input())

def read_n_int() -> list:
	return [int(s) for s in input().split()]

def list2d(row, col, init=0) -> List[list]:
	return [[init] * col for _ in range(row)]
MOD = 10 ** 9 + 7
MOD = 163577857
fact = [1] * (10 ** 5 + 1)
for i in range(1, len(fact)):
	fact[i] = i * fact[i - 1] % MOD
ifact = [1] * (10 ** 5 + 1)
ifact[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(1, len(fact) - 1)[::-1]:
	ifact[i] = ifact[i + 1] * (i + 1) % MOD

def nCr(n, i):
	if i < 0 or i > n:
		return 0
	return fact[n] * ifact[i] % MOD * ifact[n - i] % MOD
T = read_int()
for _ in range(T):
	N = read_int()
	arr = read_n_int()
	cnt = Counter(arr)
	zeros = pow(2, cnt[0], MOD)
	ans = [0] * (2 * N + 1)
	(one, n_one) = (cnt[1], cnt[-1])
	for i in range(2 * N + 1):
		k = i - N
		ans[i] = nCr(one + n_one, one - k) * zeros % MOD
	ans[N] -= 1
	print(*ans, sep=' ')


N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
NUM = 163577857
InverseofNumber(NUM)
InverseofFactorial(NUM)
factorial(NUM)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	a = 0
	b = 0
	c = 0
	for i in A:
		if i == 0:
			c += 1
		if i == 1:
			a += 1
		if i == -1:
			b += 1
	ans = [0 for i in range(2 * N + 1)]
	ans[N] = -1
	k = pow(2, c, NUM)
	for i in range(0, a + b + 1):
		ans[N - b + i] += Binomial(a + b, i, NUM) * k % NUM
	print(' '.join((str(x) for x in ans)))