CF1129C.Morse Code

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

在莫尔斯电码中，英文字母被表示为长度为 $1$ 至 $4$ 的字符串。此外，每个英文字母的莫尔斯码表示仅由“点”（dot）和“划”（dash）组成。在本题中，我们用字符 "0" 表示一个“点”，用 "1" 表示一个“划”。

由于仅含 "0" 和/或 "1"、且长度在 $1$ 到 $4$ 之间的字符串共有 $2^1+2^2+2^3+2^4 = 30$ 个，但英文字母仅有 $26$ 个，因此并非所有这 $30$ 个字符串都对应某个英文字母。具体而言，所有长度不超过 $4$ 的 "0"/"1" 字符串均唯一对应一个英文字母，除以下四个字符串外："0011"、"0101"、"1110" 和 "1111" —— 它们不对应任何英文字母。

你将处理一个初始为空的字符串 $S$。接下来共进行 $m$ 次操作，每次操作向 $S$ 末尾追加一个 "0"（点）或 "1"（划）。你的任务是：在每次向 $S$ 追加字符后，找出并报告 $S$ 中有多少个非空的英文字母序列，使得该序列可由 $S$ 的某个子串以莫尔斯码方式表示。

由于答案可能极其巨大，请对 $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$.

第一行包含一个整数 $m$（$1 \leq m \leq 3\,000$）—— 表示对字符串 $S$ 进行修改的次数。

接下来的 $m$ 行中，每行包含一个字符："0"（代表点）或 "1"（代表划），表示应将该字符追加到 $S$ 的末尾。

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

输出 $m$ 行，其中第 $i$ 行表示对字符串 $S$ 进行第 $i$ 次修改后的答案。

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.

1. "T" (translates into "1")
2. "M" (translates into "11")
3. "O" (translates into "111")
4. "TT" (translates into "11")
5. "TM" (translates into "111")
6. "MT" (translates into "111")
7. "TTT" (translates into "111")

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

我们考虑第一个样例中所有字符都追加到 $S$ 后的情形，此时 $S$ 为 "111"。

如您所见，"1"、"11" 和 "111" 均对应某个不同的英文字母。事实上，它们分别被翻译为 'T'、'M' 和 'O'。因此，所有能用 $S$ 的某个子串在摩尔斯电码中表示的非空英文字母序列如下所示：

1. "T"（翻译为 "1"）
2. "M"（翻译为 "11"）
3. "O"（翻译为 "111"）
4. "TT"（翻译为 "11"）
5. "TM"（翻译为 "111"）
6. "MT"（翻译为 "111"）
7. "TTT"（翻译为 "111"）

尽管本题无需此信息，但英文字母到摩尔斯电码的转换表可在此处找到：https://en.wikipedia.org/wiki/Morse_code