Gambling
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Niuniu likes gambling.
Team A and B will play 2n-1 matches.
Niuniu wants to bet 22n-1 that team A wins the entire series.
In other words, if A wins n or more matches, Niuniu will gain 22n - 1
If A loses(B wins) n or more matches, Niuniu will lose 22n - 1(gain -22n - 1)

However, the banker does not allow such a bet. Niuniu can only bet on individual matches.
The winning percentage of both teams is 0.5. All matches are independent of each other.

Niuniu can bet on the (i+1)-th match after seeing the results of the first i games.

Your program need read n and output the bet on the first match.
Then read the result of the first match, output the bet on the second match.
Then read the result of the second match, output the bet on the third match.
....
Finally, read the result of the (……)-th match, and team A wins or loses the entire series, the program ends.

The answer can be uniquely determined, and this is not a interactive problem.

As the result might be very large, you should output the result mod 1000000007.

输入描述:

The first line contains an integer, which is n.
The second line contains the results of contests, which are 0s and 1s.
0 means team A wins, and 1 means team A loses(team B wins)
It is guaranteed this is a legal process.

Once the number of 0 or 1 reaches n, there will be no more input.

1 <= n <= 100000

输出描述:

You should output the bet for each contest in a new line.
The number of output is the same as the second line of input.
示例1

输入

复制 
2
0 1 1

输出

复制 
4
4
8

说明

In fact, for n = 2, the bets are always 4 4 8, no matter what the outcome of the matches.

If team A (or B) wins the first two matches, Niuniu will gain 4 + 4 = 8 (or lose 4 + 4 = 8).

If team A and B both win one of the first two matches, Niuniu gains 4 - 4 = 0, and will bet 8 on the third match.

In all situations, Niuniu will gain 8 if team A wins the entire series, and will lose 8 if team A loses the entire series.
示例2

输入

复制 
3
1 1 0 0 1

输出

复制 
12
12
8
16
32

说明

The sum of all bets (with sign) is -22n-1 or 22n-1
(-12) + (-12) + (8) + (16) + (-32) = -32 = -25

示例3

输入

复制 
3
0 1 0 0

输出

复制 
12
12
16
16

说明

(12) + (-12) + (16) + (16) = 32 = 25
You can make the third bet, based on the first two result.
示例4

输入

复制 
2
1 1

输出

复制 
4
4

说明

Team A wins the first two matches. There won't be a third match.