01tree

There is a tree with $n$ nodes. Every node has a value of 0 or 1.

In one second, you can choose two adjacent nodes with the same value and flip both values.

You always spend the least number of seconds to transform a starting state into an ending state. If it is impossible to transform the starting state into the ending state, you skip it (so you spend 0 seconds).

The catch is that for some nodes, you do not remember the value (in the starting state, the ending state, or both). Over all pairs of (starting state, ending state) that agree with your memory, find the total time it takes to transform the starting state into the ending state. Print this value modulo $10^9+7$.

The first line contains an integer $t$, the number of test cases ($1 \le t \le 1000$). The test cases follow.

The first line of each test case contains one integer $n$ ($2 \le n \le 10^5$), the size of the tree.

Then $n-1$ lines follow, each containing two integers $u$ and $v$, denoting an edge that connects $u$ and $v$ in the tree.

The next line contains a string $s$ of length $n$ made of the characters 0, 1, and ?. This string is your memory of the starting state: 0 and 1 are the values of the nodes, and ? means you do not remember the value of that node.

The following line contains a string $t$ of length $n$ denoting your memory of the ending state, in the same format as the starting state.

The sum of $n$ over all test cases does not exceed $10^5$.

For each test case, print one line with a single integer: the answer modulo $10^9+7$.