시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 379 98 66 25.681%

문제

트리는 N개의 정점과 N-1개의 에지로 구성된 그래프이다. 트리의 성질 중 하나는 어느 두 정점 간에도 유일하게 하나의 경로가 존재한다는 것이다.

트리의 모든 에지에 음이 아닌 정수인 가중치가 배정되었다. ‘경로의 가중치’란 경로에 해당하는 에지들의 곱으로 정의된다. 또한 ‘트리의 가중치’는 트리 상에 가능한 모든 경로에 대해 ‘경로의 가중치’의 합을 의미한다. 문제는 트리가 주어졌을 때 ‘트리의 가중치’를 구하는 것이다.

입력

첫째 줄에 트리의 정점의 개수 N(1≤N≤100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(0≤W≤1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 에지의 가중치는 W라는 것을 의미한다.

출력

첫째 줄부터 트리의 가중치를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

3
3 2 100
2 1 100

예제 출력

10200

예제 입력 2

4
1 2 5
1 3 5
1 4 5

예제 출력 2

90

예제 입력 3

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

예제 출력 3

55

힌트