DBFS 序（困难版）

英文题名：I2. DBFS Order (Hard Version)
来源：Codeforces 2237I2
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：2 seconds
空间限制：1024 megabytes

题目描述

给定一棵有根树和每个点儿子的固定顺序。非根点颜色为 $0/1$，遍历时颜色 $0$ 的新点进队首，颜色 $1$ 的新点进队尾。字符串 $s$ 限制每个点可取颜色；困难版允许 0/1/?。求可能产生的不同遍历序列数量。

输入格式

第一行输入 $t$。每组输入 $n$、字符串 $s$ 和每个点的有序儿子列表。

输出格式

输出不同遍历序列数量，对 $10^9+7$ 取模。

样例

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