CF2237I1 DBFS Order (Easy Version)

这是本题的简单版本。不同的版本区别在于本版本中的字符串 $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 和 ? 组成。对于每个结点 $i$（$2\leq i\leq n$），$s_{i-1}$ 描述了结点 $i$ 的可能颜色： - 若 $s_{i-1} = \texttt{0}$，则结点 $i$ 的颜色必须为 $0$； - 若 $s_{i-1} = \texttt{?}$，则结点 $i$ 的颜色可以为 $0$ 或 $1$。 请你求出在所有可能的合法染色方案下，所有可能出现的不同遍历列表数量。由于结果可能过大，请对 $10^9+7$ 取模输出。

每组测试包含多组测试用例。第一行为测试用例组数 $t$（$1\leq t\leq 10^4$）。测试用例的描述如下。 对于每组测试用例，第一行为整数 $n$（$2\leq n\leq 3000$），表示树的结点数。 第二行为一个长度为 $n-1$ 的字符串 $s$，仅由字符 0 和 ? 组成。$s_i$ 描述了结点 $i+1$ 的可能颜色。 接下来 $n$ 行描述每个结点的有序子节点列表，第 $i$ 行先给出整数 $l_i$（$0\leq l_i\leq n-1$），表示第 $i$ 个结点的子节点个数。随后 $l_i$ 个不同的整数 $a_{i,1},a_{i,2},\ldots,a_{i,l_i}$，表示第 $i$ 个结点的子节点，顺序给出。 保证所给顺序子节点列表描述了一棵以 $1$ 为根的有根树。 保证所有测试用例中 $\sum n^2 \leq 9 \cdot 10^6$。

每组测试用例输出一行一个整数，表示在所有合法染色情况下可能出现的不同遍历列表的数量，对 $10^9+7$ 取模。

设 $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$ 为根的星型，所有 $5$ 个叶子结点颜色任意。染色为 $0$ 的叶子被立即访问，染色为 $1$ 的会等所有儿子被考虑完才访问。在 $2^5$ 种染色中，共有 $27$ 种不同遍历列表。 第三个测试用例中，颜色自由的结点是 $2,3,4,5,6,8,12$，颜色固定为 $0$ 的是 $c_7=0$，$c_9=0$，$c_{10}=0$，$c_{11}=0$。在 $2^7$ 种合法染色方案中，共有 $75$ 种不同的遍历列表。 由 ChatGPT 5 翻译