Expected Score in Shooting Subtrees

doby is an archer who loves arrows. At an archery range, there are (n) targets labeled from (1) to (n) arranged such that (n-1) lines connect them to form a tree with root (1). Each target has a score. To train, doby chooses a node (called the parent point) and shoots every target in its subtree (including itself) exactly once. Each shot hits its target independently with probability (50%). If a target is hit, its score is counted; otherwise, a factor of (1) is used. Thus, the score for one subtree is defined as the product of the scores of all hit targets.

The expected score for a subtree rooted at a node (v) is given by [ E_v = \prod_{u \in \text{subtree}(v)} \frac{s_u+1}{2}, ] where (s_u) is the score on target (u).

Your task is to compute the sum of the expected scores for all possible choices of the parent point (i.e. for every node in the tree) modulo (19260817).

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), representing the number of targets.\nThe second line contains (n) space-separated integers (s_1, s_2, \ldots, s_n), where (s_i) denotes the score on the (i)-th target.\nEach of the next (n-1) lines contains two integers (u) and (v) ((1 \le u,v \le n)), indicating that there is an edge between targets (u) and (v) in the tree. It is guaranteed that these edges form a tree rooted at (1).

outputFormat

Output a single integer, which is the sum of the expected scores for all choices of the parent point (i.e. for every node in the tree), taken modulo (19260817).

sample

3
1 3 5
1 2
1 3

11