Maximum Subtree Score

You are given a tree with N nodes. Each node has an associated integer value. A subtree is defined as any connected subset of nodes forming a tree. The score of a subtree is defined as the product of the values of all nodes in that subtree. Formally, if a subtree contains the nodes in the set S, its score is given by:

\(score = \prod_{i \in S} value_i \;\bmod\; 10^9+7\)

Your task is to find the maximum score among all possible subtrees of the given tree.

Note: The tree is unrooted and the input edges connect the nodes. You may assume that the tree is connected.

inputFormat

The first line contains an integer N (the number of nodes).

The second line contains N space-separated integers representing the values assigned to the nodes (from node 1 to node N).

Each of the next N-1 lines contains two space-separated integers u and v indicating that there is an edge between node u and node v.

outputFormat

Output a single integer: the maximum subtree score modulo \(10^9+7\).

3
2 3 4
1 2
1 3

24