Tree Designer Hoseok

Hoseong, who loves trees more than anything, is a bonsai tree expert. Every tree Hoseong grows consists of vertices and edges. The vertices are numbered $1$ through $N$, and each edge connects two distinct vertices. The number of vertices is exactly one more than the number of edges, and no cycle exists. The root of the tree is one of the vertices, the one at the lowest height among all vertices. Vertex 1 is always guaranteed to be the root, and a leaf is a vertex with at most one incident edge. A vertex closer to the root sits at a lower height, and one farther away sits at a higher height.

The trees Hoseong grows are special: each vertex has an integer from $0$ to $9$ written on it. One day Hoseong suddenly wanted to make a Christmas tree, and decided to choose one or more vertices to hang lights on. The vertices must be chosen along the path from the root to some leaf. The chosen lights do not have to be consecutive. The vertices with lights light up, and the numbers written on them shine brightly.

Suppose the leftmost picture is the tree Hoseong has. The middle and right pictures are examples of correct light choices. Reading the numbers on the lit lights from bottom to top in each picture gives $\{0, 0, 8\}$ and $\{3, 6, 3\}$.

If the chosen lights are vertices 1, 7, and 10, the result is the left picture. This is not a valid choice because they were not chosen along the path from the root to some leaf. For the same reason, choosing lights 4, 5, 8, and 9 is also invalid.

After hearing Hoseong's requirements, Tree Designer Hoseok thought of a problem. When lights are hung, and the numbers are read from low height to high height, he wondered how many ways there are to hang the lights so that the sequence is nondecreasing. A nondecreasing sequence is one where each number is not smaller than the previous one. That is, a number equal to the previous one still satisfies nondecreasing order. For example, $\{0, 0, 8\}$ is nondecreasing, but $\{3, 6, 3\}$ is not.

Given Hoseong's tree, compute the answer Hoseok wants.

The first line gives the number of vertices $N$.

The second line gives the numbers written on vertices $1$ through $N$, separated by spaces. Each number is a natural number from $0$ to $9$.

From the third line, $N-1$ lines follow, each giving the numbers of the two vertices connected by an edge.

The given tree is guaranteed to be a single connected graph.

Print the number of ways to hang the lights modulo 1,000,000,007.

• $1 ≤ N ≤ 100,000$