CF2237I2 DBFS Order (Hard Version)

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

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

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

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.