문제

함수 $\text{randint}(l, r)$이 $[l, r]$ 범위 내의 정수 중 하나를 독립적이고 균등하게 무작위로 선택하여 반환한다고 하자.

소원이는 다음 두 단계를 거쳐 정점 번호가 $1$부터 $N$ ($2 \le N \le 2 \cdot 10^5$)까지인 무작위 라벨이 붙은 트리를 생성한다.

1. 정점 번호가 $1$부터 $N$까지인 $N$개의 정점으로 시작한다. $i$를 $2$부터 $N$까지 변화시키며, 정점 $i$와 $\text{randint}(1, i-1)$ 사이를 잇는 간선을 추가한다.
2. $\{1, 2, \ldots, N\}$의 순열 $p_1, p_2, \dots, p_N$을 균등한 확률로 무작위하게 하나 선택한다. 모든 정점 $v$의 번호를 $p_v$로 바꾼다.

지훈이는 최종적으로 생성된 트리의 간선 집합을 보고, 위 과정을 통해 정확히 이 간선 집합을 가진 트리가 생성되었을 확률을 알고 싶어 한다. 이 확률을 $10^9+7$로 나눈 나머지를 구하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

각 테스트 케이스의 첫째 줄에 정점의 개수 $N$이 주어진다.

다음 $N-1$개의 줄에 트리의 간선을 나타내는 두 정수 $u$와 $v$가 공백으로 구분되어 주어진다. ($1 \le u, v \le N$)

주어지는 간선들은 항상 트리를 이룸이 보장된다. 또한, 모든 테스트 케이스에 대한 $N$의 합은 $5 \cdot 10^5$을 초과하지 않는다.

출력

각 테스트 케이스마다 구하고자 하는 확률을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다. (확률은 기약분수로 나타낼 수 있으며, $10^9+7$에 대한 모듈러 역원을 이용하여 정수 형태로 출력한다.)

예제 입력 1

4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 4

예제 출력 1

1
333333336
83333334
55555556

제한

• 서브태스크 1: $N \le 8$
• 서브태스크 2: $N \le 2000$
• 서브태스크 3: 추가적인 제약 조건이 없다.