Connected Same Color Subsets in Modified Tree Graph

Given a tree with n nodes (1-indexed), each node is assigned a color. In addition to the original tree edges, an extra edge is added between every pair of distinct nodes whose distance in the tree is exactly 2. Let the resulting graph be \(G(V,E)\).

A nonempty subset \(V' \subseteq V\) is called connected if the induced graph \(G(V',E')\) is connected. Here, the induced edge set is defined as \(E' = \{ (u,v) \mid (u,v) \in E,~ u,v \in V' \}\).

Your task is to count the total number of nonempty subsets \(V'\) such that:

• All nodes in \(V'\) have the same color, and
• The induced subgraph \(G(V',E')\) is connected.

Since the answer can be very large, output it modulo \(10^9+7\).

Note on the extra edges: For each node \(u\) in the tree, if \(v\) and \(w\) are two distinct neighbors of \(u\), then an edge is added between \(v\) and \(w\) (if not already present). This means that in \(G\), two nodes of the same color, even if not adjacent in the original tree, might become adjacent because they are both distance 2 apart in the tree.

inputFormat

The first line contains an integer \(n\) denoting the number of nodes in the tree.

The second line contains \(n\) space-separated tokens; the \(i\)th token denotes the color of node \(i\) (colors can be strings or integers).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (1-indexed), representing an edge between nodes \(u\) and \(v\) in the tree.

outputFormat

Output a single integer: the number of connected subsets whose vertices all have the same color in the modified graph, taken modulo \(10^9+7\).

sample

3
1 2 1
1 2
2 3

3