有一棵包含 $n$ 个节点的树，每个节点的值为 $0$ 或 $1$。 在每一秒内，你可以选择两个值相同的相邻节点，并将它们的值同时翻转。

给定一个初始状态和一个目标状态，你总是花费最少的时间将初始状态转换为目标状态。如果无法将初始状态转换为目标状态，则跳过该情况（即花费 $0$ 秒）。

问题在于，对于某些节点，你不记得它们的值（在初始状态、目标状态或两者中均是如此）。请计算在所有与你的记忆相符的（初始状态，目标状态）对中，将初始状态转换为目标状态所需的时间总和。输出该值对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示树的大小。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树中连接 $u$ 和 $v$ 的边。 接下来一行包含一个长度为 $n$ 的字符串 $s$，由字符 “0”、“1” 和 “?” 组成。该字符串表示你对初始状态的记忆：“0” 和 “1” 表示节点的值，“?” 表示你不记得该节点的值。 接下来一行包含一个长度为 $n$ 的字符串 $t$，表示你对目标状态的记忆，格式与初始状态相同。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

3
2
1 2
00
11
3
1 2
2 3
???
???
3
1 2
2 3
??1
0?0

输出 1

1
16
1