Threads to the Waking Cats

Time limit: 5000 msMemory limit: 256 MB

There is one cat at every vertex of a weighted tree. The vertices are numbered $1,2,\ldots,N$ , and every edge has a positive integer length.

Initially, only the cat at vertex $1$ is awake. The remaining $N-1$ cats wake up in a uniformly random order, so each of the $(N-1)!$ possible orders is equally likely.

When the cat at vertex $v$ wakes up, it stretches a thread along the unique tree path to a cat that was already awake and whose vertex is as close as possible to $v$ . The length of this thread is the distance between the two vertices. If several already-awake cats are tied for the minimum distance, any of them may be chosen because the thread length is the same.

Every awakened cat remains at its own vertex. Threads do not affect later choices.

Find the expected sum of the lengths of all threads.

Input

The first line contains an integer $N$ ( $1 \le N \le 3000$ ), the number of vertices and cats.

Each of the next $N-1$ lines contains three integers $a$ , , and (, , ), describing an edge of length between vertices and .

Output

Let the expected total thread length be the reduced fraction $P/Q$ . Print

P \cdot Q^{-1} \bmod 998244353,

where is the multiplicative inverse of modulo .

Samples

Sample 1

Input

Output

The only cat is already awake, so no thread is stretched.

Sample 2

Input

Output

499122199

For this tree, the expected total thread length is $45/2$ . Its value modulo $998244353$ is $499122199$ .

Threads to the Waking Cats

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions