트리 경로 분해

루트가 없는 트리가 주어진다. 각 노드에는 정수가 하나씩 쓰여 있다.

트리를 경로의 집합으로 분해하는 방법의 수를 구하는 프로그램을 작성하시오. 분해는 다음 두 조건을 지켜야 한다.

• 모든 노드는 정확히 하나의 경로에 속한다.
• 한 경로에 속한 노드에 쓰여 있는 정수의 합은 음이 아니다.

여기서 경로는 트리의 간선을 따라 노드를 일렬로 이은 부분 그래프이고, 노드 하나짜리 경로도 경로로 센다. 노드를 묶은 결과가 다르면 서로 다른 분해다.

첫째 줄에 노드의 개수 $N$이 주어진다 ($1 \le N \le 10^5$). 둘째 줄에는 1번 노드부터 $N$번 노드까지 각 노드에 쓰여 있는 정수가 순서대로 주어진다. 각 정수의 절댓값은 $10^4$ 이하이다.

셋째 줄부터 $N-1$개의 줄에는 간선으로 이어진 두 노드의 번호가 주어진다. 주어지는 그래프는 항상 트리이다.

첫째 줄에 조건을 만족하는 분해 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 예제에서는 네 가지 분해가 가능하다.

• 트리 전체가 하나의 경로다. 합이 $1+10+5+(-1)=15$이므로 조건을 만족한다.
• 2번과 4번을 잇는 경로, 1번과 3번을 잇는 경로로 나눈다. 두 경로의 합은 각각 $10+(-1)=9$, $1+5=6$이다.
• 1번, 2번, 4번을 잇는 경로와 3번 하나짜리 경로로 나눈다.
• 2번과 4번을 잇는 경로, 1번 하나짜리 경로, 3번 하나짜리 경로로 나눈다.