I2. Порядок DBFS (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии строка $$$s$$$ может также содержать символ 1. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Вам дано корневое дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. Для каждой вершины её дети заданы в фиксированном порядке.

Каждая вершина, кроме корня, имеет цвет: $$$0$$$ или $$$1$$$. Для фиксированной раскраски определим следующий обход.

p <- пустой список
q <- дек, содержащий только вершину 1

пока q не пуст:
    v <- первый элемент q
    если v не находится в p:
        добавить v в конец p
    если все дети v уже находятся в p или в q:
        удалить первый элемент из q
    иначе:
        u <- первый ребёнок v, который не находится ни в p, ни в q
        если color[u] = 0:
            добавить u в начало q
        иначе:
            добавить u в конец q

После завершения процесса список $$$p$$$ называется списком обхода данной раскраски. Можно показать, что $$$p$$$ всегда является перестановкой $$$1,2,\ldots,n$$$. В частности, если все цвета равны $$$0$$$, то $$$p$$$ является прямым порядком обхода дерева в глубину (DFS preorder); если все цвета равны $$$1$$$, то $$$p$$$ является порядком обхода в ширину (BFS), где дети посещаются в заданном порядке.

Вам дана строка $$$s$$$ длины $$$n-1$$$, состоящая из символов 0, 1 и ?. Для каждой вершины $$$i$$$ при $$$2\le i\le n$$$ символ $$$s_{i-1}$$$ описывает возможный цвет вершины $$$i$$$:

  • если $$$s_{i-1}=\texttt{0}$$$, то вершина $$$i$$$ должна иметь цвет $$$0$$$;
  • если $$$s_{i-1}=\texttt{1}$$$, то вершина $$$i$$$ должна иметь цвет $$$1$$$;
  • если $$$s_{i-1}=\texttt{?}$$$, то вершина $$$i$$$ может иметь цвет $$$0$$$ или $$$1$$$.

Найдите количество различных списков обхода, которые можно получить при всех допустимых раскрасках. Так как ответ может быть большим, выведите его по модулю $$$10^9+7$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных..

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 3000$$$) — количество вершин в дереве.

Вторая строка содержит строку $$$s$$$ длины $$$n-1$$$. В сложной версии $$$s$$$ состоит из символов 0, 1 и ?. Символ $$$s_i$$$ описывает возможный цвет вершины $$$i+1$$$.

Следующие $$$n$$$ строк описывают упорядоченные списки детей. $$$i$$$-я из этих строк сначала содержит целое число $$$l_i$$$ ($$$0 \le l_i \le n-1$$$) — количество детей вершины $$$i$$$. Затем следуют $$$l_i$$$ различных целых чисел $$$a_{i,1},a_{i,2},\ldots,a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le n$$$) — дети вершины $$$i$$$ в их порядке.

Гарантируется, что заданные упорядоченные списки детей описывают корневое дерево с корнем $$$1$$$.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$9 \cdot 10^6$$$.

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

Для каждого набора входных данных выведите единственное целое число — количество различных списков обхода $$$p$$$, которые можно получить при всех допустимых назначениях цветов, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
10
4
1??
2 2 3
0
1 4
0
6
?????
5 2 3 4 5 6
0
0
0
0
0
12
?????1?010?
1 11
2 8 3
3 9 12 6
0
1 4
0
1 10
0
1 5
0
2 2 7
0
2
1
1 2
0
5
1?0?
1 2
1 3
1 4
1 5
0
5
1111
4 2 3 4 5
0
0
0
0
3
??
2 2 3
0
0
5
1???
2 2 3
2 4 5
0
0
0
7
?1?0??
2 2 3
2 4 5
2 6 7
0
0
0
0
8
1?0??1?
3 2 3 4
2 5 6
1 7
0
0
1 8
0
0
Выходные данные
3
27
88
1
1
1
2
6
8
14
Примечание

Пусть $$$c_i$$$ — цвет вершины $$$i$$$.

В первом наборе входных данных вершина $$$2$$$ должна иметь цвет $$$1$$$, тогда как вершины $$$3$$$ и $$$4$$$ свободны.

Если $$$(c_3,c_4)=(0,0)$$$, список обхода равен $$$[1,3,4,2]$$$.

Если $$$(c_3,c_4)=(0,1)$$$, список обхода равен $$$[1,3,2,4]$$$.

Если $$$(c_3,c_4)=(1,0)$$$ или $$$(c_3,c_4)=(1,1)$$$, список обхода равен $$$[1,2,3,4]$$$.

Таким образом, существует $$$3$$$ различных списка обхода.

Во втором наборе входных данных дерево является звездой с корнем в вершине $$$1$$$, и все пять листьев имеют свободные цвета. Лист с цветом $$$0$$$ посещается немедленно при его рассмотрении, тогда как лист с цветом $$$1$$$ откладывается до тех пор, пока не будут рассмотрены все дети корня. Среди всех $$$2^5$$$ допустимых назначений цветов существует $$$27$$$ различных списков обхода.

В третьем наборе входных данных свободными вершинами являются $$$2,3,4,5,6,8,12$$$. Фиксированные цвета: $$$c_7=1$$$, $$$c_9=0$$$, $$$c_{10}=1$$$ и $$$c_{11}=0$$$. Среди всех $$$2^7$$$ допустимых назначений цветов существует $$$88$$$ различных списков обхода.