네트워크 신뢰도

N개의 노드로 이루어진 트리 형태의 통신 네트워크가 있다. 각 간선에는 1 이상 9 이하의 가중치(신뢰도)가 있다.

모든 노드 쌍 (a, b) (a < b)에 대해, a에서 b로 가는 경로 상의 간선 가중치의 곱을 구한 뒤, 이 곱들의 총합을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드 수 N이 주어진다. (2 <= N <= 100,000)
둘째 줄부터 N-1개의 줄에 간선 정보 a, b, w가 공백으로 구분되어 주어진다. (1 <= a, b <= N, 1 <= w <= 9)

출력

모든 노드 쌍의 경로 가중치 곱의 총합을 1,000,000,007로 나눈 나머지를 출력한다.

입출력 예시

입력 1

3
1 2 3
2 3 5

출력 1

23

입력 2

4
1 2 2
1 3 3
1 4 4

출력 2

35