완전 이진 트리(perfect binary tree)란 모든 리프가 아닌 노드가 정확히 두 개의 자식을 가지며, 모든 리프 노드가 루트로부터 같은 거리에 있는 루트가 있는 트리를 의미합니다.
루트가 없는 완전 이진 트리(unrooted perfect binary tree)란 특정 노드를 루트로 잡았을 때 완전 이진 트리가 되는 트리를 의미합니다.
베시는 $N$ ($1 \le N \le 10^5$)개의 노드로 이루어진 트리를 가지고 있습니다. 트리의 간선 중 일부를 제거하여 남은 숲이 루트가 없는 완전 이진 트리들의 집합이 되도록 하는 방법의 수를 구하세요. 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력하세요.
입력
첫 번째 줄에는 독립적인 테스트 케이스의 수 $T$ ($1 \leq T \leq 100$)가 주어집니다.
각 테스트 케이스의 첫 번째 줄에는 $N$이 주어집니다.
각 테스트 케이스의 다음 $N-1$개의 줄에는 간선을 나타내는 두 정수 $u_i$와 $v_i$ ($1 \leq u_i, v_i \leq N$)가 주어집니다.
각 테스트 케이스에서 주어진 간선들은 $N$개의 노드로 이루어진 트리를 형성함이 보장됩니다.
또한, 모든 테스트 케이스에 대한 $N$의 합은 $2\cdot 10^5$를 넘지 않습니다.
출력
각 테스트 케이스마다 간선을 제거하여 루트가 없는 완전 이진 트리들의 숲을 만드는 방법의 수를 $10^9+7$로 나눈 나머지를 출력하세요.
예제
예제 입력 1
3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 5예제 출력 1
8
2
14참고
첫 번째 테스트 케이스에서 베시는 다음 간선 부분집합 중 하나를 제거하여 완전 이진 트리들의 숲을 얻을 수 있습니다:
- $(2, 6)$
- $(1, 2)$, $(2, 3)$, $(2, 6)$
- $(1, 2)$, $(2, 3)$, $(4, 6)$
- $(1, 2)$, $(2, 3)$, $(5, 6)$
- $(1, 2)$, $(4, 6)$, $(5, 6)$
- $(2, 6)$, $(4, 6)$, $(5, 6)$
- $(2, 3)$, $(4, 6)$, $(5, 6)$
- $(1, 2)$, $(2, 3)$, $(2, 6)$, $(4, 6)$, $(5, 6)$
첫 번째 부분집합은 높이가 $1$인 두 개의 서브트리를 만들고, 마지막 부분집합은 높이가 $0$인 여섯 개의 서브트리를 만들며, 나머지 부분집합들은 높이가 $0$인 세 개의 서브트리와 높이가 $1$인 하나의 서브트리를 만듭니다.
서브태스크
- 입력 2-3: $N\le 15$
- 입력 4-5: 어떤 노드도 2개보다 많은 노드와 인접하지 않음.
- 입력 6-9: $N\le 1000$, $N$의 합은 $2000$을 넘지 않으며, 어떤 노드도 3개보다 많은 노드와 인접하지 않음.
- 입력 10-13: 어떤 노드도 3개보다 많은 노드와 인접하지 않음.
- 입력 14-21: 추가 제약 없음.