C. Азбука Морзе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В азбуке Морзе каждая буква латинского алфавита определена как строка некоторый длины от $$$1$$$ до $$$4$$$, состоящая из точек и тире. В этой задаче мы будем обозначать точку как «0», а тире как «1».

Так как существует $$$2^1+2^2+2^3+2^4 = 30$$$ строк длины от $$$1$$$ до $$$4$$$, состоящих только из «0» и «1», не все из них соответствуют какой-то из $$$26$$$ букв латинского алфавита. А именно, все строки из «0» и/или «1» длины не более $$$4$$$ соответствуют разным буквы латинского алфавита, кроме следующих четырех строк, которые ничему не соответствуют: «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$$$-я из которых должна содержать ответ после $$$i$$$-й модификации $$$S$$$.

Примеры
Входные данные
3
1
1
1
Выходные данные
1
3
7
Входные данные
5
1
0
1
0
1
Выходные данные
1
4
10
22
43
Входные данные
9
1
1
0
0
0
1
1
0
1
Выходные данные
1
3
10
24
51
109
213
421
833
Примечание

Рассмотрим первый тестовый пример, после того, как к $$$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»)

Хоть это и не нужно в этой задаче, таблица переводов букв латинского алфавита в азбуку Морзе: здесь.