The problem setter is lazy and does not want to write a long problem statement, nor do they want to read one. The problem setter is kind and does not want the contestants to read a long problem statement. Therefore, this problem statement is very brief:

Given a tree with $n$ nodes. The node labeled $i$ has a weight $a_i$. A pair of paths on the tree can be represented as $(x, y, u, v)$, where $x \le y$ and $u \le v$, representing a path from $x$ to $y$ and a path from $u$ to $v$.

Define the value of a path pair $f(x, y, u, v)$ as the least common multiple (lcm) of the weights of all nodes that are present on both paths. Calculate the product of the values of all possible path pairs, i.e.,

$$\prod_{1 \le x \le y \le n, 1 \le u \le v \le n} f(x, y, u, v)$$

Since the result can be very large, you only need to output the answer modulo $10^9 + 7$.

Input

The first line contains an integer $n$, representing the size of the tree. The second line contains $n$ integers, where the $i$-th number represents the weight $a_i$ of the $i$-th node. The next $n - 1$ lines each contain two integers $u_i, v_i$, representing an edge in the tree.

Output

Output a single integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

4
2 2 1 4
1 2
2 3
2 4

Output 1

248320570

Constraints

For 20% of the data, $n \le 100, a_i \le 11$; For 30% of the data, $n \le 2000, a_i \le 11$; For 50% of the data, $n \le 2 \times 10^4$; For 60% of the data, $n \le 8 \times 10^4, a_i \le 10^4$; For 80% of the data, $n \le 2 \times 10^5, a_i \le 5 \times 10^5$; For 100% of the data, $n \le 5 \times 10^5, a_i \le 5 \times 10^6$.