트리 짝짓기

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

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

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

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

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

• $1\le T\le 10\, 000$.
• $1\le N\le 100\, 000$.
• $1\le u_i < v_i\le 2N$.
• $1\le c_i\le 10^9$.
• 주어진 그래프는 항상 트리 구조임이 보장된다.
• 모든 테스트 케이스에서 $N$의 합은 $100\, 000$을 넘지 않는다.