대세는 바이러스야

준표는 던전을 클리어하고자 한다. 던전은 트리구조이며, 던전을 클리어하기 위해선 보스방에 사는 던전의 보스를 죽여야 한다. 보스방은 언제나 1번 정점에 있다.

보스방을 제외한 던전의 모든 단말정점에는 던전에 입장할 수 있는 입구가 있으며, 보스방에 들어가는 문은 유일하다. 즉 1번 정점에는 오직 하나의 간선만이 연결되어있다.

던전에는 보스 외에도 몬스터가 산다. 던전의 각 방마다 최대 한 마리의 몬스터가 서식할 수 있고, 준표가 보스방에 도달하기 위해선 경로를 막고있는 몬스터를 모두 죽여야 한다.

<그림 1> 던전의 예시

보스를 제외한 몬스터들은 던전에서 하나의 군집을 이루고 있어 던전의 연속된 일부분을 차지하고 있다.

<그림 2> 예제 1의 가능한 군집들. 빨간 사각형의 군집은 던전의 연속된 일부분을 차지하지 않아 있을 수 없는 군집이다.

준표에게는 무시무시한 병기가 있는데, g번 바이러스를 사용하면 유전자 g를 가지는 모든 몬스터들을 죽일 수 있는 생화학 병기다.

각 몬스터의 유전자는 하나의 양의 정수로 나타낼 수 있으며, 유전자 g를 가진다는 의미는 몬스터의 유전자가 g로 나누어떨어진다는 뜻이다.

즉, 죽이고자 하는 몬스터들의 "유전자의 공약수" 번 바이러스를 사용하면 모든 몬스터가 죽는다.

당연하지만 모든 유전자는 1로 나누어떨어지기 때문에 1번 바이러스를 사용하면 모든 몬스터를 죽일 수 있을 것이다.

하지만 번호가 낮을수록 가격이 비싸기 때문에 준표는 가능하면 가장 높은 번호의 바이러스를 사용한다. 즉, 준표는 죽이고자 하는 몬스터들의 "유전자의 최대공약수" 번 바이러스를 사용한다.

준표가 어떤 군집의 던전을 클리어하기 위해 사용하는 바이러스 번호를 치트키라고 하자. 준표는 가능한 모든 군집의 치트키의 총합을 구하고자 한다.

첫 줄에 던전의 크기 N이 입력된다. (2 ≤ N ≤ 100,000)

두 번째 줄에 던전의 i번 방에 서식할 수 있는 몬스터의 유전자 gi 가 순서대로 입력된다. (1 ≤ gi ≤ 1,000,000,000)

세 번째 줄부터 N - 1줄에 걸쳐 던전의 구조가 u v 형태로 입력된다. 이는 u번 방과 v번 방을 잇는 통로가 있다는 의미이다. (1 ≤ u*, v* ≤ N)

각 입구에서 출발했을 때 가능한 모든 군집의 치트키의 총합을 공백으로 구분하여 정점 번호순으로 출력한다.

매우 큰 수가 될 수 있으므로 109+7 로 나눈 나머지로 출력한다.