You are given a tree of n nodes, some of the nodes contain numbers and others don't. Your task is to compute the number of ways to complete the labeling of the tree rooted at 1, such that the following condition is satisfied "for any subtree x all elements of the subtree must divide its root".

Input:

First line contains a single integer n, denoting the number of nodes in the tree.
Next Line contains n integers, each number describes the content of a node in order (e.g: first number describes content of node 1, second describes content of node 2, ... etc). If a number is 0, it means that the content is unknown.
Next $n-1$ lines contain each two numbers $(u, v)$, meaning that there is an edge between node u and node v.

Output:

Ouput a single integer denoting the number of ways to fill the tree without breaking the constraint modulo $10^9+7$;

Constraints:

• $1 \le n \le 10^5$.
• All numbers are non negative and less than or equal 10^9.
• The root's content is always known.