Tree path decomposition

You are given a tree with no root. Each node has one integer written on it.

Write a program that counts the ways to decompose the tree into a set of paths. A decomposition has to satisfy both conditions below.

• Every node belongs to exactly one path.
• The sum of the integers written on the nodes of a path is nonnegative.

A path here is a subgraph whose nodes are joined one after another along the edges of the tree, and a path that holds a single node counts as a path. Two decompositions are different when they group the nodes differently.

The first line contains the number of nodes $N$ ($1 \le N \le 10^5$). The second line contains the integers written on node 1 through node $N$, in that order. Each integer has absolute value at most $10^4$.

Each of the next $N-1$ lines contains the numbers of the two nodes joined by an edge. The given graph is always a tree.

Print the number of decompositions that satisfy the conditions, modulo $10^9+7$.

The first example has four decompositions.

• The whole tree is one path. Its sum is $1+10+5+(-1)=15$, so it satisfies the condition.
• One path joins nodes 2 and 4, the other joins nodes 1 and 3. The two sums are $10+(-1)=9$ and $1+5=6$.
• One path joins nodes 1, 2 and 4, and the other holds node 3 alone.
• One path joins nodes 2 and 4, and the remaining two paths hold node 1 alone and node 3 alone.