시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 793 227 159 30.114%

문제

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

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

입력

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

출력

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

예제 입력 1

3
3 2 100
2 1 100

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6IjEyODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQyYjhcdWI5YWNcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWFjZmMgTi0xXHVhYzFjXHVjNzU4IFx1YzVkMFx1YzljMFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzc0XHViMmU0LiBcdWQyYjhcdWI5YWNcdWM3NTggXHVjMTMxXHVjOWM4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQgXHVjNWI0XHViMjkwIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVhYzA0XHVjNWQwXHViM2M0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNWQwXHVjOWMwXHVjNWQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1YWMwMCBcdWJjMzBcdWM4MTVcdWI0MThcdWM1YzhcdWIyZTQuICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yjc4MCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzVkMFx1YzljMFx1YjRlNFx1Yzc1OCBcdWFjZjFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWI2MTBcdWQ1NWMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViMjk0IFx1ZDJiOFx1YjlhYyBcdWMwYzFcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHViMzAwXHVkNTc0ICZsc3F1bztcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4JnJzcXVvO1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVkMmI4XHViOWFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgJmxzcXVvO1x1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNTgmcnNxdW87XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSZsZTtOJmxlOzEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggQSwgQiwgVygwJmxlO1cmbGU7MSwwMDApXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxOFx1YjI5NFx1YjM3MCBcdWM3NzRcdWIyOTQgQVx1YzgxMFx1YWNmYyBCXHVjODEwXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAgXHVjNzc0IFx1YzVkMFx1YzljMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgV1x1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQVVRFVkkiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIHlvdSBhcmUgYm91bmQgdG8ga25vdyBieSBub3csIGEgdHJlZSBpcyBhIGNvbm5lY3RlZCBncmFwaCBjb25zaXN0aW5nIG9mIE4gdmVydGljZXMgYW5kIE4mbWludXM7MSBlZGdlcy4gVHJlZXMgYWxzbyBoYXZlIHRoZSBwcm9wZXJ0eSBvZiB0aGVyZSBiZWluZyBleGFjdGx5IGEgc2luZ2xlIHVuaXF1ZSBwYXRoIGJldHdlZW4gYW55IHBhaXIgb2YgdmVydGljZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgdHJlZSBpbiB3aGljaCBldmVyeSBlZGdlIGlzIGFzc2lnbmVkIGEgd2VpZ2h0ICZuZGFzaDsgYSBub24tbmVnYXRpdmUgaW50ZWdlci4gVGhlIHdlaWdodCBvZiBhIHBhdGggaXMgdGhlIHByb2R1Y3Qgb2YgdGhlIHdlaWdodHMgb2YgYWxsIGVkZ2VzIG9uIHRoZSBwYXRoLiBUaGUgd2VpZ2h0IG9mIHRoZSB0cmVlIGlzIHRoZSBzdW0gb2YgdGhlIHdlaWdodHMgb2YgYWxsIHBhdGhzIGluIHRoZSB0cmVlLiBQYXRocyBnb2luZyBpbiBvcHBvc2l0ZSBkaXJlY3Rpb25zIChBIHRvIEIgYW5kIEIgdG8gQSkgYXJlIGNvbnNpZGVyZWQgdGhlIHNhbWUgYW5kLCB3aGVuIGNhbGN1bGF0aW5nIHRoZSB3ZWlnaHQgb2YgYSB0cmVlLCBhcmUgY291bnRlZCBvbmx5IG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiBhIHRyZWUsIGNhbGN1bGF0ZXMgaXRzIHdlaWdodCBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgdHJlZS4gVGhlIHZlcnRpY2VzIGFyZSBudW1iZXJlZCAxIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOJm1pbnVzOzEgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiBhbmQgVyAoMSAmbGU7IEEsIEIgJmxlOyBOLCAwICZsZTsgVyAmbGU7IDEwMDApIGRlc2NyaWJpbmcgb25lIGVkZ2UuIFRoZSBlZGdlIGNvbm5lY3RzIHZlcnRpY2VzIEEgYW5kIEIsIGFuZCBpdHMgd2VpZ2h0IGlzIFcuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSB3ZWlnaHQgb2YgdGhlIHRyZWUsIG1vZHVsbyAxIDAwMCAwMDAgMDA3LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==