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. 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}=0), then vertex (i) must have color (0); if (s_{i-1}=1), then vertex (i) must have color (1); if (s_{i-1}=?), 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). 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