Tổng GCD Trên Đường Đi Tổ Tiên

Cho một cây có gốc gồm $n$ đỉnh, gốc tại đỉnh $1$. Mỗi đỉnh $v$ có một giá trị $x_v$ là số nguyên không âm không vượt quá ${10}^{12}$.

Đỉnh $u$ được gọi là tổ tiên của đỉnh $v$ nếu $u$ nằm trên đường đi ngắn nhất từ gốc tới $v$ (mỗi đỉnh cũng được coi là tổ tiên của chính nó).

Với cặp $(u,v)$ mà $u$ là tổ tiên của $v$, giả sử các đỉnh trên đường đi từ $u$ tới $v$ là $u=t_1,t_2,\dots ,t_k=v$. Định nghĩa

$$f(u,v)=gcd(x_{t_1},x_{t_2},\dots ,x_{t_k}).$$

Đặc biệt $f(u,u)=x_u$, và quy ước $gcd(0,y)=gcd(y,0)=y$, kể cả $gcd(0,0)=0$.

Yêu cầu: tính

$$\sum _{u\text{ là tổ tiên của }v}f(u,v)\left(\mathrm{mod}{10}^9+7\right).$$

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a,b$ mô tả một cạnh nối hai đỉnh $a$ và $b$ của cây.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng cần tính, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le x_i\le {10}^{12}$
• $1\le a,b\le n$, $a\ne b$
• Đồ thị cho trước là một cây liên thông.

Ví dụ