F. ЛЕГОндарный гроссмейстер
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Устав играть с мелками, вы решили перейти на Лего! Сегодня у вас есть длинная полоска высоты $$$1$$$ и длины $$$n$$$, в некоторых ячейках которой расположены детальки Лего $$$1$$$ на $$$1$$$.

За одну секунду, вы можете либо убрать две последовательные детальки Лего с полоски (если таковые имеются), либо поставить две детальки Лего на последовательные позиции (если они пустые). Вы можете ставить и убирать Лего только по две штуки за раз, так как ваши пальцы слишком широкие для одной детальки.

Вам интересно узнать, сколько времени вы потратите на игру с Лего. При этом, для вас крайне важна эффективность, а потому если вы хотите получить из некоторого стартового состояния некоторое финишное, то вы всегда потратите наименьшее количество секунд. Если же из стартового состояния невозможно получить финишное, то вы просто ничего не станете делать (то есть потратите $$$0$$$ секунд).

Проблема в том, что вы не помните, были ли детальки Лего в некоторых позициях (как в стартовом состоянии, так и в финишном). А потому вы хотите посчитать суммарное время получения финишного состояния из стартового для всех пар (стартовое состояние, финишное состояние), которые не противоречат вашей памяти. Так как время может оказаться очень большим, выведите его по модулю $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \leq n \leq 2000$$$) — размер полоски Лего.

Во второй строке каждого набора задана строка $$$s$$$ длины $$$n$$$, состоящая из символов 0, 1 и ? — то, что вы помните о стартовом состоянии:

  • 1 означает позицию, в которой совершенно точно стояла деталька Лего,
  • 0 означает позицию, в которой совершенно точно не было детальки Лего,
  • а ? означает позицию, про которую вы ничего не помните.

В третьей строке каждого набора задана строка $$$t$$$ длины $$$n$$$, состоящая из символов 0, 1 и ? — то, что вы помните о финишном состоянии, в том же формате, что и для стартового состояния.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — ответ на задачу по модулю $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Пример
Входные данные
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
Примечание

В первом наборе входных данных, $$$00$$$ — единственное возможное стартовое состояние, а $$$11$$$ — единственное возможное финишное состояние. Потребуется одна операция, чтобы превратить $$$00$$$ в $$$11$$$.

Во втором наборе, ниже приведены некоторые из возможных пар стартовых и финишных состояний:

  • $$$(000, 011)$$$ — потребуется $$$1$$$ операция;
  • $$$(001, 100)$$$ — потребуется $$$2$$$ операции;
  • $$$(010, 000)$$$ — потребуется $$$0$$$ операций, так как невозможно получить из заданного стартового состояния заданное финишное.