В азбуке Морзе каждая буква латинского алфавита определена как строка некоторый длины от \(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\) строк, \(i\)-я из которых должна содержать ответ после \(i\)-й модификации \(S\).
Примечание
Рассмотрим первый тестовый пример, после того, как к \(S\) будут дописаны все буквы, т.е. «111».
Как вы можете видеть, «1», «11» и «111» соответствуют каким-то буквам латинского алфавита. Более точно, они переводятся в 'T', 'M', и в 'O', соответственно. Все слова, которые переводятся в подстроку строки \(S\) в азбуке Морзе, таким образом, равны:
- «T» (переводится в «1»)
- «M» (переводится в «11»)
- «O» (переводится в «111»)
- «TT» (переводится в «11»)
- «TM» (переводится в «111»)
- «MT» (переводится в «111»)
- «TTT» (переводится в «111»)
Хоть это и не нужно в этой задаче, таблица переводов букв латинского алфавита в азбуку Морзе: здесь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
1
1
|
1
3
7
|
|
2
|
5
1
0
1
0
1
|
1
4
10
22
43
|
|
3
|
9
1
1
0
0
0
1
1
0
1
|
1
3
10
24
51
109
213
421
833
|