D - 操作

题目背景

浪花淘尽，唯我屹立不倒

题目描述

给定一棵树。现在每个点有点权 $0$ 或 $1$ 。

我们可以进行操作，一次操作可以选择一条边 $(u,v)$ ，如果 $u,v$ 点权相同则同时改变点权，即从 $0$ 变成 $1$ 或从 $1$ 变成 $0$ 。否则不变。

对于序列 $s$ 和 $t$ ，我们定义 $f(s,t)$ 为点权序列从 $s$ 变成 $t$ 的最小操作次数，如果无法完成则为 $0$ 。

现在我们给出序列 $a$ 和 $b$ ，我们希望求出 $f(a,b)$ 。可是因为一些原因，$a$ 和 $b$ 的一些位置被抹去了，在输入中用问号代替。现在，我们希望对于所有可能的 $(a,b)$ ，求出 $f(a,b)$ 的和，答案对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $n$ ，表示树的点数。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$ ，表示树的一条边 $(u_i,v_i)$。

接下来一行包含一个字符串，第 $i$ 个字符代表 $a_i$ 的值。

接下来一行包含一个字符串，第 $i$ 个字符代表 $b_i$ 的值。

输出格式

输出一行一个整数，表示所有可能的 $(a,b)$ 的 $f(a,b)$ 之和对 $10^9+7$ 取模的结果。

样例

样例输入

3
1 2
2 3
???
???

样例输出

16

数据范围

对于所有数据，$1\le n\le 5*10^5$，$1\le u_i,v_i\le n$ ，$a_i,b_i\in$ {0,1,?}。

子任务 1 ( 10% ) ： $n\le 5$ 。

子任务 2 ( 20% ) ： $n\le 300$ 。

子任务 3 ( 20% ) ： $n\le 3000$ 。

子任务 4 ( 20% ) ：$a_i,b_i=$? 。

子任务 5 ( 30% ) ：无特殊限制。