Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Kamil and Making a Stream

time limit per test

4 secondsmemory limit per test

768 megabytesinput

standard inputoutput

standard outputKamil 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, \dots, 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}, \dots, 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$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$) — the number of vertices in the tree.

The following line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le 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 \le a, b \le n$$$, $$$a \neq b$$$) — the vertices connected by a single edge.

Output

Output the sum of the beauties on all paths $$$(u, v)$$$ such that $$$u$$$ is ancestor of $$$v$$$. This sum should be printed modulo $$$10^9 + 7$$$.

Examples

Input

5 4 5 6 0 8 1 2 1 3 1 4 4 5

Output

42

Input

7 0 2 3 0 0 0 0 1 2 1 3 2 4 2 5 3 6 3 7

Output

30

Note

The following figure shows all $$$10$$$ possible paths for which one endpoint is an ancestor of another endpoint. The sum of beauties of all these paths is equal to $$$42$$$:

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/05/2020 21:02:17 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|