James has a tree with $n$ nodes $n-1$ edges where the $i^{{th}}$ edge has a length, $w_i$. He wants to play a game involving $n$ moves. During each move, he performs the following steps:

Randomly chooses some node $x_i$ from the tree. Each node has an equal probability of being chosen.
Calculates the distance from node $x_i$ to each node reachable from $x_i$ using one or more edges.
Deletes node $x_i$.

For example, the diagram below shows what happens when we choose a random node and delete it from the tree:

After $n$ moves, the tree is empty and the game ends.

James defines the magic number, $m$, as the sum of all numbers calculated in step $2$ of each move. Let $E_{m}$ be the expected value of $m$.

Give the tree's edges and their respective lengths, calculate and the print the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)$. It is guaranteed that $E_m\times n!$ is an integer.

Note

Due to a bug in the system, you might see accepted verdict in this problem even if you don't pass all the test cases. Please ignore that verdict, only the score you get is important in the ranklist.

Input Format

The first line contains an integer, $n$, denoting the number of nodes. 

Each of the $n-1$ subsequent lines contains three space-separated integers describing the respective values of $u_i$, $v_i$, and $w_i$, meaning that there is an edge of length $w_i$ connecting nodes $u_i$ and $v_i$.  

Constraints

$1\leq n\leq5000$
$1\leq u_i,v_i\leq n$
$1\leq w_i\leq10^9$

Subtasks

For $30\%$ of the max score $n\leq10$
For ${60\%}$ of the max score $n\leq400$

Output Format

Print a single integer denoting the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)$.

Sample Input
3
2 1 2
3 2 3

Sample Output
50

Explanation

Let $d(u,v)$ be the distance between node ${u}$ and node ${v}$. Here are the ${6}$ different variants:

$(x_1,x_2,x_3)=(1,2,3)$

$(x_1,x_2,x_3)=(2,1,3)$

$(x_1,x_2,x_3)=(1,3,2)$. $m=7+3+0=10$

$(x_1,x_2,x_3)=(2,3,1)$. $m=0+5+0=5$
$(x_1,x_2,x_3)=(3,1,2)$. $m=2+0+8=10$
$(x_1,x_2,x_3)=(3,2,1)$. $m=0+2+8=10$

The expected value of the magic number is $E_m=\frac{50}{6}$. We then print the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)=(\frac{50}{6}\times3!)\ \text{mod}\ (10^9+9)=50$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Probability


Solutions:
import math
import os
import random
import re
import sys
from collections import defaultdict
from itertools import product
import math
from functools import lru_cache, reduce
p = 1000000009

class Node:

	def __init__(self):
		self.nf = set()
		self.out_edges = dict()

	def add(self, v):
		self.nf.add(v)
		self.out_edges[v] = dict()
		return self

	def __len__(self):
		return len(self.out_edges)

class Graph2:

	def __init__(self):
		self.V = defaultdict(Node)
		self.w = dict()

	def add_edge(self, u, v, w):
		self.w[min(u, v), max(u, v)] = w
		self.V[u].add(v)
		self.V[v].add(u)
		return self

	def leaves(self):
		return set((u for (u, node) in self.V.items() if len(node) == 1))

	def node(self, u):
		return self.V[u]

	def weight(self, u, v):
		(u, v) = (u, v) if u < v else (v, u)
		return self.w[u, v]

	def __len__(self):
		return len(self.V)

	def calc_freqs(self):
		updateables = self.leaves()
		while updateables:
			v = updateables.pop()
			updateables.update(update_freq(v, self))

def freq_sum(node, v, w=0):
	freq = dict()
	freq[2] = (w, 1)
	for (u, e) in node.out_edges.items():
		if u == v:
			continue
		for (k, (f, n)) in e.items():
			(f0, n0) = freq.get(k + 1, (0, 0))
			freq[k + 1] = ((f0 + f + n * w) % p, n0 + n)
	return freq

def update_freq(u, G):
	node = G.node(u)
	assert len(node.nf) <= 1
	nodes = node.nf if len(node.nf) == 1 else node.out_edges.keys()
	updateable = set()
	for v in nodes:
		other = G.node(v)
		if not other.nf:
			continue
		if u in other.nf:
			other.nf.discard(u)
			other.out_edges[u] = freq_sum(node, v, G.weight(u, v))
		if len(other.nf) <= 1:
			updateable.add(v)
	return updateable

class FacModp:

	def __init__(self):
		self.x = 1

	def __call__(self, i):
		x = self.x
		self.x = self.x * i % p
		return x

def factorial_per_k(n):
	f = FacModp()
	x = [f(i) for i in range(1, n + 1)]
	f = FacModp()
	y = [f(i) for i in range(n, 0, -1)]
	return [xi * yi % p for (xi, yi) in zip(x, reversed(y))]

def get_magic(G):
	G.calc_freqs()
	magic = 0
	fac_per_k = factorial_per_k(len(G))
	for node in G.V.values():
		magic = sum((v * fac_per_k[k - 1] % p for out in node.out_edges.values() for (k, (v, n)) in out.items()), start=magic % p)
	return magic % p
n = int(input())
G = Graph2()
for _ in range(n - 1):
	(u, v, w) = map(int, input().split())
	G.add_edge(u, v, w)
print(get_magic(G))