B"Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached 100 million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him? You're given a tree -- a connected undirected graph consisting of n vertices connected by n - 1 edges. The tree is rooted at vertex 1 . A vertex u is called an ancestor of v if it lies on the shortest path between the root and v . In particular, a vertex is an ancestor of itself. Each vertex v is assigned its beauty x_v -- a non-negative integer not larger than 10^{12} . This allows us to define the beauty of a path. Let u be an ancestor of v . Then we define the beauty f(u, v) as the greatest common divisor of the beauties of all vertices on the shortest path between u and v . Formally, if u=t_1, t_2, t_3, ... , t_k=v are the vertices on the shortest path between u and v , then f(u, v) = gcd(x_{t_1}, x_{t_2}, ... , x_{t_k}) . Here, gcd denotes the greatest common divisor of a set of numbers. In particular, f(u, u) = gcd(x_u) = x_u . Your task is to find the sum sum_{u text{ is an ancestor of }v} f(u, v). As the result might be too large, please output it modulo 10^9 + 7 . Note that for each y , gcd(0, y) = gcd(y, 0) = y . In particular, gcd(0, 0) = 0 . The first line contains a single integer n ( 2 <= n <= 100 ,000 ) -- the number of vertices in the tree. The following line contains n integers x_1, x_2, ... , x_n ( 0 <= x_i <= 10^{12} ). The value x_v denotes the beauty of vertex v . The following n - 1 lines describe the edges of the tree. Each of them contains two integers a, b ( 1 <= a, b <= n , a neq b ) -- the vertices connected by a single edge. Output the sum of the beauties on all paths "...