In 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$.

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$.

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