문제

정점이 개인 트리가 주어진다. 모그는 이 트리의 모든 정점을 두 개씩 짝지어 총 개의 쌍으로 분할하려 한다. 분할의 비용은 개의 쌍 전체에 대해 각 쌍에 속하는 두 정점 사이의 거리의 합이다. 두 정점 사이의 거리는 트리에서 두 정점을 잇는 유일한 경로에 포함된 간선 가중치의 합이다. 이때, 비용을 최소로 하여 분할하는 경우의 수를 구해보자. 두 분할이 서로 다르다고 함은, 적어도 한 정점이 서로 다른 정점과 짝지어지는 경우를 말하며, 쌍들의 나열 순서는 고려하지 않는다.

입력

첫째 줄에 테스트 케이스의 개수 가 주어진다.

각 테스트 케이스의 첫째 줄에 양의 정수 이 주어진다.

각 테스트 케이스의 둘째 줄부터 개의 줄에 걸쳐 가 공백으로 구분되어 주어진다. 이는 정점 와 사이에 가중치가 인 간선이 존재함을 뜻한다. ;

주어진 그래프는 항상 트리 구조임이 보장된다.

모든 테스트 케이스에서 의 합은 을 넘지 않는다.

출력

각 테스트 케이스마다 분할하는 경우의 수를 으로 나눈 나머지를 한 줄에 하나씩 출력한다.

노트

첫 번째 테스트 케이스에서 로 나눴을 때, 각 쌍의 비용 합이 로 최소이다. 따라서 가지가 가능하다.