I2. DBFS Order (Hard Version)
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version, the string $$$s$$$ may also contain character 1. You can hack only if you solved all versions of this problem.

You are given a rooted tree with $$$n$$$ vertices, rooted at vertex $$$1$$$. For each vertex, its children are given in a fixed order.

Each vertex except the root has a color, either $$$0$$$ or $$$1$$$. For a fixed coloring, define the following traversal.

p <- empty list
q <- deque containing only vertex 1

while q is not empty:
    v <- the front element of q
    if v is not in p:
        append v to p
    if every child of v is already in p or in q:
        pop the front element from q
    else:
        u <- the first child of v that is neither in p nor in q
        if color[u] = 0:
            push u to the front of q
        else:
            push u to the back of q

After the process ends, the list $$$p$$$ is called the traversal list of this coloring. It can be shown that $$$p$$$ is always a permutation of $$$1,2,\ldots,n$$$. In particular, if all colors are $$$0$$$, then $$$p$$$ is the DFS preorder of the tree; if all colors are $$$1$$$, then $$$p$$$ is the BFS order of the tree, where children are visited in the given order.

You are given a string $$$s$$$ of length $$$n-1$$$, consisting of characters 0, 1, and ?. For each vertex $$$i$$$ with $$$2\le i\le n$$$, the character $$$s_{i-1}$$$ describes the possible color of vertex $$$i$$$:

  • if $$$s_{i-1}=\texttt{0}$$$, then vertex $$$i$$$ must have color $$$0$$$;
  • if $$$s_{i-1}=\texttt{1}$$$, then vertex $$$i$$$ must have color $$$1$$$;
  • if $$$s_{i-1}=\texttt{?}$$$, then vertex $$$i$$$ may have color $$$0$$$ or $$$1$$$.

Find the number of distinct traversal lists that can be obtained over all valid colorings. Since the answer may be large, output it modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows..

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the number of vertices in the tree.

The second line contains a string $$$s$$$ of length $$$n-1$$$. In the hard version, $$$s$$$ consists of characters 0, 1, and ?. The character $$$s_i$$$ describes the possible color of vertex $$$i+1$$$.

The next $$$n$$$ lines describe the ordered lists of children. The $$$i$$$-th of these lines first contains an integer $$$l_i$$$ ($$$0 \le l_i \le n-1$$$) — the number of children of vertex $$$i$$$. Then follow $$$l_i$$$ distinct integers $$$a_{i,1},a_{i,2},\ldots,a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le n$$$) — the children of vertex $$$i$$$ in their order.

It is guaranteed that the given ordered children lists describe a rooted tree with root $$$1$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$9 \cdot 10^6$$$.

Output

For each test case, output a single integer — the number of distinct traversal lists $$$p$$$ that can be generated over all valid color assignments, modulo $$$10^9 + 7$$$.

Example
Input
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
Output
3
27
88
1
1
1
2
6
8
14
Note

Let $$$c_i$$$ be the color of vertex $$$i$$$.

In the first test case, vertex $$$2$$$ must have color $$$1$$$, while vertices $$$3$$$ and $$$4$$$ are free.

If $$$(c_3,c_4)=(0,0)$$$, the traversal list is $$$[1,3,4,2]$$$.

If $$$(c_3,c_4)=(0,1)$$$, the traversal list is $$$[1,3,2,4]$$$.

If $$$(c_3,c_4)=(1,0)$$$ or $$$(c_3,c_4)=(1,1)$$$, the traversal list is $$$[1,2,3,4]$$$.

Thus there are $$$3$$$ distinct traversal lists.

In the second test case, the tree is a star rooted at vertex $$$1$$$, and all five leaves have free colors. A leaf with color $$$0$$$ is visited immediately when it is considered, while a leaf with color $$$1$$$ is postponed until after all children of the root have been considered. Among all $$$2^5$$$ valid color assignments, there are $$$27$$$ distinct traversal lists.

In the third test case, the free vertices are $$$2,3,4,5,6,8,12$$$. The fixed colors are $$$c_7=1$$$, $$$c_9=0$$$, $$$c_{10}=1$$$, and $$$c_{11}=0$$$. Among all $$$2^7$$$ valid color assignments, there are $$$88$$$ distinct traversal lists.