I2. DBFS Order (Hard Version)

Source: Codeforces 2237I2
Contest: Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
Time limit: 2 seconds
Memory limit: 1024 megabytes

Statement

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$.

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.

Examples

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