Устав играть с мелками, вы решили перейти на Лего! Сегодня у вас есть длинная полоска высоты \(1\) и длины \(n\), в некоторых ячейках которой расположены детальки Лего \(1\) на \(1\).
За одну секунду, вы можете либо убрать две последовательные детальки Лего с полоски (если таковые имеются), либо поставить две детальки Лего на последовательные позиции (если они пустые). Вы можете ставить и убирать Лего только по две штуки за раз, так как ваши пальцы слишком широкие для одной детальки.
Вам интересно узнать, сколько времени вы потратите на игру с Лего. При этом, для вас крайне важна эффективность, а потому если вы хотите получить из некоторого стартового состояния некоторое финишное, то вы всегда потратите наименьшее количество секунд. Если же из стартового состояния невозможно получить финишное, то вы просто ничего не станете делать (то есть потратите \(0\) секунд).
Проблема в том, что вы не помните, были ли детальки Лего в некоторых позициях (как в стартовом состоянии, так и в финишном). А потому вы хотите посчитать суммарное время получения финишного состояния из стартового для всех пар (стартовое состояние, финишное состояние), которые не противоречат вашей памяти. Так как время может оказаться очень большим, выведите его по модулю \(1\,000\,000\,007\) (\(10^9 + 7\)).
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу по модулю \(1\,000\,000\,007\) (\(10^9 + 7\)).
Примечание
В первом наборе входных данных, \(00\) — единственное возможное стартовое состояние, а \(11\) — единственное возможное финишное состояние. Потребуется одна операция, чтобы превратить \(00\) в \(11\).
Во втором наборе, ниже приведены некоторые из возможных пар стартовых и финишных состояний:
- \((000, 011)\) — потребуется \(1\) операция;
- \((001, 100)\) — потребуется \(2\) операции;
- \((010, 000)\) — потребуется \(0\) операций, так как невозможно получить из заданного стартового состояния заданное финишное.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
00
11
3
???
???
3
??1
0?0
4
??0?
??11
5
?????
0??1?
10
?01??01?1?
??100?1???
|
1
16
1
14
101
1674
|