F. Finding the Best Guess
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Huron Casino is running a strange gambling game on trees. The game consists on guessing the final value of the number $$$S$$$ generated for the algorithm described below:

Given a tree with $$$n$$$ nodes, where each node has an integer $$$a_i$$$ written on it, and an integer $$$S$$$ initially equal to $$$0$$$. The algorithm consists on repeating the following steps $$$n$$$ times:

  1. Choose a random node $$$u$$$ that has not been removed yet. All nodes that have not been removed have the same probability of been chosen.
  2. Add $$$a_v$$$ to $$$S$$$ for all the nodes $$$v$$$, such that there is a path from $$$u$$$ to $$$v$$$ passing through nodes and edges that have not been removed yet.
  3. Remove $$$u$$$ and all the edges incident to it.

The game is played for a certain number of participants. The player (or players) whose guess is closer to the final value of $$$S$$$ is the winner of the game.

You are an expert on greedy algorithms, for that reason you think that betting for the expected value of $$$S$$$ is the best strategy. Write a program that finds the expected value of $$$S$$$.

Input

The first line contain an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^5$$$).

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$) indicating that there is an edge connecting nodes $$$u$$$ and $$$v$$$.

Output

It can be shown that the expected value of $$$S$$$ can be expressed as an irreducible fraction $$$P/Q$$$ such that $$$P$$$ and $$$Q$$$ are non-negative integers. Print $$$P \cdot Q^{-1}$$$ modulo $$$998244353$$$.

Examples
Input
2
1 1
1 2
Output
3
Input
6
1 5 6 6 8 2
1 2
1 3
3 4
3 5
2 6
Output
465847442