Codeforces Global Round 18 |
---|
Закончено |
Устав играть с мелками, вы решили перейти на Лего! Сегодня у вас есть длинная полоска высоты $$$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 и ? — то, что вы помните о стартовом состоянии:
В третьей строке каждого набора задана строка $$$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$$$.
Во втором наборе, ниже приведены некоторые из возможных пар стартовых и финишных состояний:
Название |
---|