CF2237I1.DBFS Order (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the string $s$ contains no 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 listq <- deque containing only vertex 1while 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$.

这是该问题的简单版本。两个版本的区别在于，在此版本中，字符串 $s$ 不包含字符 1。仅当您解决了该问题的所有版本时，才可进行 hack。

给定一棵含 $n$ 个顶点的有根树，根节点为顶点 $1$。对每个顶点，其子节点以固定顺序给出。

除根节点外，每个顶点均有一种颜色，为 $0$ 或 $1$。对于一个固定的染色方案，定义如下遍历过程：

p <- 空列表  
q <- 双端队列，初始仅含顶点 1  
while q 非空:  
    v <- q 的前端元素  
    if v 不在 p 中:  
        将 v 追加至 p  
    if v 的所有子节点均已位于 p 或 q 中:  
        从 q 前端弹出元素  
    else:  
        u <- v 的第一个既不在 p 中也不在 q 中的子节点  
        if color[u] = 0:  
            将 u 推入 q 前端  
        else:  
            将 u 推入 q 后端  

该过程结束后，列表 $p$ 称为该染色方案对应的遍历列表。可以证明，$p$ 恒为 $1,2,\ldots,n$ 的一个排列。特别地，若所有颜色均为 $0$，则 $p$ 即为该树的深度优先搜索（DFS）先序遍历；若所有颜色均为 $1$，则 $p$ 即为该树的广度优先搜索（BFS）遍历（子节点按给定顺序访问）。

给定一个长度为 $n-1$ 的字符串 $s$，由字符 0、1 和 ? 组成。对每个满足 $2\le i\le n$ 的顶点 $i$，字符 $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$ 取模的结果。

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 easy version, $s$ consists only of characters 0 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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 3000$）——树中顶点的数量。

第二行包含一个长度为 $n-1$ 的字符串 $s$。在简单版本中，$s$ 仅由字符 0 和 ? 组成。字符 $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$。

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

对于每个测试用例，输出一个整数——在所有有效的染色方案下可生成的不同遍历序列 $p$ 的数量，对 $10^9 + 7$ 取模。

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

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

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

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

If $(c_2,c_4)=(1,1)$, the traversal list is $[1,3,2,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=0$, $c_9=0$, $c_{10}=0$, and $c_{11}=0$. Among all $2^7$ valid color assignments, there are $75$ distinct traversal lists.

令 $c_i$ 表示顶点 $i$ 的颜色。

在第一个测试用例中，顶点 $3$ 的颜色必须为 $0$，而顶点 $2$ 和 $4$ 的颜色可自由选择。

若 $(c_2,c_4)=(0,0)$ 或 $(c_2,c_4)=(0,1)$，则遍历序列为 $[1,2,3,4]$；
若 $(c_2,c_4)=(1,0)$，则遍历序列为 $[1,3,4,2]$；
若 $(c_2,c_4)=(1,1)$，则遍历序列为 $[1,3,2,4]$。

因此共有 $3$ 种不同的遍历序列。

在第二个测试用例中，该树是以顶点 $1$ 为根的星形树，全部五个叶子节点的颜色均可自由选择。颜色为 $0$ 的叶子节点在其被考虑时立即被访问，而颜色为 $1$ 的叶子节点则被推迟至根节点的所有子节点均被考虑完毕后再访问。在全部 $2^5$ 种合法的颜色赋值方案中，共有 $27$ 种不同的遍历序列。

在第三个测试用例中，可自由赋色的顶点为 $2,3,4,5,6,8,12$；固定颜色为 $c_7=0$、$c_9=0$、$c_{10}=0$ 和 $c_{11}=0$。在全部 $2^7$ 种合法的颜色赋值方案中，共有 $75$ 种不同的遍历序列。