Đây là phiên bản khó của bài toán. Điểm khác biệt giữa hai phiên bản là trong phiên bản này, chuỗi \(s\) có thể chứa cả ký tự \(1\). Bạn chỉ có thể hack nếu đã giải được tất cả các phiên bản của bài toán này.

Bạn được cho một cây có gốc gồm \(n\) đỉnh, được chọn gốc là đỉnh \(1\). Với mỗi đỉnh, các đỉnh con của nó được cho theo một thứ tự cố định.

Mỗi đỉnh ngoại trừ đỉnh gốc có một màu, hoặc \(0\) hoặc \(1\). Với một cách tô màu cố định, ta định nghĩa phép duyệt như sau:

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

Sau khi quá trình kết thúc, danh sách \(p\) được gọi là danh sách duyệt của cách tô màu đó.

Có thể chứng minh rằng \(p\) luôn là một hoán vị của \(1,2,\ldots,n\).

Đặc biệt, nếu tất cả các màu đều là \(0\), thì \(p\) chính là thứ tự DFS preorder của cây; nếu tất cả các màu đều là \(1\), thì \(p\) chính là thứ tự BFS của cây, trong đó các đỉnh con được xét theo thứ tự đã cho.

Bạn được cho một chuỗi \(s\) có độ dài \(n-1\), gồm các ký tự \(0\), \(1\) và ?.

Với mỗi đỉnh \(i\) (\(2\le i\le n\)), ký tự \(s_{i-1}\) mô tả màu có thể có của đỉnh \(i\):

• Nếu \(s_{i-1}=0\), đỉnh \(i\) bắt buộc phải có màu \(0\).
• Nếu \(s_{i-1}=1\), đỉnh \(i\) bắt buộc phải có màu \(1\).
• Nếu \(s_{i-1}=?\), đỉnh \(i\) có thể có màu \(0\) hoặc \(1\).

Yêu cầu: Tìm số lượng danh sách duyệt khác nhau có thể thu được từ tất cả các cách tô màu hợp lệ.

Vì đáp án có thể rất lớn, hãy in kết quả theo modulo \(10^9+7\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1\le t\le 10^4\)) — số lượng bộ test.
• Với mỗi bộ test:
• Dòng đầu tiên chứa số nguyên \(n\) (\(2\le n\le 3000\)) — số đỉnh của cây.
• Dòng thứ hai chứa chuỗi \(s\) có độ dài \(n-1\), gồm các ký tự \(0\), \(1\) và ?.
• \(n\) dòng tiếp theo mô tả danh sách các đỉnh con của từng đỉnh.

Ở dòng thứ \(i\), đầu tiên là số nguyên \(l_i\) (\(0\le l_i\le n-1\)) — số lượng con của đỉnh \(i\).

Sau đó là \(l_i\) số nguyên \(a_{i,1},a_{i,2},\ldots,a_{i,l_i}\) (\(1\le a_{i,j}\le n\)) — các đỉnh con của \(i\), được cho theo thứ tự cố định.

Dữ liệu đảm bảo các danh sách con được cho tạo thành một cây có gốc là đỉnh \(1\).

Dữ liệu cũng đảm bảo tổng \(n^2\) trên tất cả các bộ test không vượt quá \(9\cdot10^6\).

Output

Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng danh sách duyệt \(p\) khác nhau có thể được tạo ra từ tất cả các cách tô màu hợp lệ.

In đáp án modulo \(10^9+7\).

Example

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