Oyler's Geometric Jumps

The road from Oyler’s home to his school has $n$steps, where his home is at step $1$ and his school is at step $n$. Everyday, Oyler starts his journey from step $1$ and goes to step $n$. To move from one step to another step, Oyler makes jumps of length that are powers of two. So, from step $i$ Oyler can only go to step $j$ if $j-i$ is a nonnegative power of $2$ ($j>i$). For example, if he wants to go from step $1$ to step $10$, the sequence of steps Oyler crosses can be $1, 5, 6, 8, 10$.

Today the steps of the path were coloured with colours $1, \cdots, n$. In particular, step $i$ was coloured in colour $c_i$. Seeing the colourful steps, Oyler came up with a game. Starting from today, on day $i$, Oyler will avoid the steps with color $i$. Thus an interesting problem was born. In how many ways can Oyler make the journey on day $i$? You need to answer this for each of days $1, 2, \cdots, n$. Since the answers will be large, you have to output it modulo $10^9+7.$

Input

In the first line, you will be given a positive integer $n$, the number of steps. In the next line, you will be given $n$ space separated integers, they are the integers $c_1, c_2, \cdots, c_n$.

$1 \leq n \leq 5\times10^5$

$1 \leq c_i \leq n$

Output

Output $n$ integers in $n$ lines. The $i$ the integers will be the number of ways Oyler can make the journey on day $i .$

Sample

10
1 2 1 2 4 6 8 3 3 9

0
24
11
38
98
38
98
44
0
98