Morse Code

题意翻译

## 题目描述 在摩尔斯电码（以下简称“摩码”）中，字母表中的一个字母被表示为一个长度为$1$~$4$的01串。长度为$1$~$4$的01串共有$2^1+2^2+2^3+2^4=30$个，而字母只有$26$个，所以有$4$个01串不表示任何字母——"0011"、"0101"、"1110"、"1111"，其他$26$个01串表示互不相同的$26$个字母。 你有一个01串$S$，初始为空。现在有$m$次添加，每次往$S$的末尾添加一个字符（"0"或"1"）。对于每一次添加，你都要回答目前的$S$的所有非空子串用摩码所能表示的字母串的总数。由于答案可能巨大，你只需要输出答案模$10^9+7$的结果。 ## 输入格式 第$1$行：一个整数$m$——添加的次数。 第$2$~$m+1$行：一个整数，$0$或$1$——每次添加的字符。 ## 输出格式 $m$行：每一次添加之后的答案。

题目描述

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

输入输出样例

输入样例 #1

3
1
1
1

输出样例 #1

1
3
7

输入样例 #2

5
1
0
1
0
1

输出样例 #2

1
4
10
22
43

输入样例 #3

9
1
1
0
0
0
1
1
0
1

输出样例 #3

1
3
10
24
51
109
213
421
833

说明

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](https://en.wikipedia.org/wiki/Morse_code).