Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Morse Code

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn Morse code, an letter of English alphabet is represented as a string of some length from $$$1$$$ to $$$4$$$. Moreover, each Morse code representation of an English letter contains only dots and dashes. In this task, we will represent a dot with a "0" and a dash with a "1".

Because there are $$$2^1+2^2+2^3+2^4 = 30$$$ strings with length $$$1$$$ to $$$4$$$ containing only "0" and/or "1", not all of them correspond to one of the $$$26$$$ English letters. In particular, each string of "0" and/or "1" of length at most $$$4$$$ translates into a distinct English letter, except the following four strings that do not correspond to any English alphabet: "0011", "0101", "1110", and "1111".

You will work with a string $$$S$$$, which is initially empty. For $$$m$$$ times, either a dot or a dash will be appended to $$$S$$$, one at a time. Your task is to find and report, after each of these modifications to string $$$S$$$, the number of non-empty sequences of English letters that are represented with some substring of $$$S$$$ in Morse code.

Since the answers can be incredibly tremendous, print them modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$m$$$ ($$$1 \leq m \leq 3\,000$$$) — the number of modifications to $$$S$$$.

Each of the next $$$m$$$ lines contains either a "0" (representing a dot) or a "1" (representing a dash), specifying which character should be appended to $$$S$$$.

Output

Print $$$m$$$ lines, the $$$i$$$-th of which being the answer after the $$$i$$$-th modification to $$$S$$$.

Examples

Input

3

1

1

1

Output

1

3

7

Input

5

1

0

1

0

1

Output

1

4

10

22

43

Input

9

1

1

0

0

0

1

1

0

1

Output

1

3

10

24

51

109

213

421

833

Note

Let us consider the first sample after all characters have been appended to $$$S$$$, so S is "111".

As you can see, "1", "11", and "111" all correspond to some distinct English letter. In fact, they are translated into a 'T', an 'M', and an 'O', respectively. All non-empty sequences of English letters that are represented with some substring of $$$S$$$ in Morse code, therefore, are as follows.

- "T" (translates into "1")
- "M" (translates into "11")
- "O" (translates into "111")
- "TT" (translates into "11")
- "TM" (translates into "111")
- "MT" (translates into "111")
- "TTT" (translates into "111")

Although unnecessary for this task, a conversion table from English alphabets into Morse code can be found here.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/29/2020 12:27:28 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|