Consider a sequence $A$ of $N$ integers, where the absolute value of each element is limited to 1. For every value $x$ in the range $-N$ to $N$, find the count of non-empty subsequences of $A$ whose sum of elements equals $x$. The answer should be printed modulo $10^9 + 7$.

Input format:

First line contains $N$, the number of elements in the array

Next line contain $N$ spaced integers the elements of the array $A$

Output format:

Print $2*N$ spaced integers denoting the count of non-empty subsequences of $A$  for every value $x$ in the range $-N$ to $N$ 

Constraints: 

$1<=N<=10^5 \\ |A_i| <= 1$