Oyler's Geometric Jumps

upobir Criterion 2022 Round 17
Limits 2s, 512 MB

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

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

Input

In the first line, you will be given a positive integer nn, the number of steps. In the next line, you will be given nn space separated integers, they are the integers c1,c2,,cnc_1, c_2, \cdots, c_n.

1n5×1051 \leq n \leq 5\times10^5

1cin1 \leq c_i \leq n

Output

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

Sample

InputOutput
10
1 2 1 2 4 6 8 3 3 9
0
24
11
38
98
38
98
44
0
98

Submit

Login to submit.

Statistics

80% Solution Ratio
NirjhorEarliest, 1M ago
NirjhorFastest, 0.8s
NirjhorLightest, 31 MB
NirjhorShortest, 1365B
Toph uses cookies. By continuing you agree to our Cookie Policy.