01tree

트리가 있고, 노드는 $n$개이다. 각 노드의 값은 0 또는 1이다.

1초마다 서로 인접한 두 노드 중 값이 같은 노드를 골라, 두 노드의 값을 모두 뒤집을 수 있다.

시작 상태를 끝 상태로 바꾸는 데 드는 최소 초를 항상 쓴다. 시작 상태를 끝 상태로 바꿀 수 없으면 그 쌍은 건너뛰며, 0초를 쓴다.

문제는 일부 노드의 값을 기억하지 못한다는 점이다. 시작 상태, 끝 상태, 또는 둘 다에서 값을 모르는 노드가 있을 수 있다. 기억과 일치하는 모든 (시작 상태, 끝 상태) 쌍에 대해, 시작 상태를 끝 상태로 바꾸는 데 걸리는 시간의 총합을 구하라. 이 값을 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 1000$). 테스트 케이스가 그 뒤를 잇는다.

각 테스트 케이스의 첫 줄에는 트리의 크기 $n$ ($2 \le n \le 10^5$)이 주어진다.

이어서 $n-1$개의 줄에 각각 트리에서 간선으로 연결된 두 노드 $u$와 $v$가 주어진다.

다음 줄에는 길이 $n$의 문자열 $s$가 주어진다. 이는 시작 상태에 대한 기억이며, 0과 1은 노드의 값을, ?는 값을 기억하지 못함을 뜻한다.

그다음 줄에는 같은 형식으로 끝 상태에 대한 기억을 나타내는 길이 $n$의 문자열 $t$가 주어진다.

모든 테스트 케이스의 $n$의 합은 $10^5$를 넘지 않는다.

각 테스트 케이스마다 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나의 정수로 출력한다.