在摩尔斯电码中,英文字母表中的字母表示为从 $$$1$$$ 到 $$$4$$$ 的某个长度的字符串。此外,英语字母的每个摩尔斯电码表示仅包含点和破折号。在此任务中,我们将用“0”表示点,用“1”表示破折号。
因为存在 $$$2^1+2^2+2^3+2^4 = 30$$$ 个长度为 $$$1$$$ 到 $$$4$$$ 且仅包含“0”和/或“1”的字符串,所以并非所有这些字符串都对应于 $$$26$$$ 英文字母之一。特别地,每个长度至多$$$4$$$的“0”和/或“1”字符串翻译成不同的英文字母,除了以下四个不对应于任何英文字母的字符串:“0011”、“0101”、“1110”和“1111”。
您将使用字符串 $$$S$$$,该字符串最初为空。对于 $$$m$$$ 次,将在 $$$S$$$ 上附加一个点或破折号,一次一个。您的任务是在对字符串 $$$S$$$ 进行每次修改后,查找并报告用摩尔斯电码 $$$S$$$ 的某些子字符串表示的非空英文字母序列的数量。
由于答案可能非常巨大,请以 $$$10^9 + 7$$$ 为模打印它们。
输入
第一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 3\,000$$$) — 对 $$$S$$$ 的修改次数。
接下来的 $$$m$$$ 行包含“0”(代表点)或“1”(代表破折号),指定应将哪个字符附加到 $$$S$$$。
输出
打印$$$m$$$行,其中第$$$i$$$行是对$$$S$$$进行第$$$i$$$修改后的答案。
示例
输入 #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
注意
让我们考虑将所有字符附加到 $$$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”)
虽然此任务不需要,但可以在此处找到从英语字母到摩尔斯电码的转换表。