Werewolves#13022

Werewolves

2 seconds
512 megabytes
Very hard

You are given a colored tree on nodes, node has color c_i. As a reminder, a tree on nodes is a connected graph with n-1 edges.

Compute the number of connected subgraphs of this tree, for which there exists some color (majority color), such that strictly more than half of the nodes of this subgraph have this color.

Since the answer can be quite large, compute it modulo .

Input

The first line of input contains one integer (1 \le n \le 3000) — the number of nodes in the tree.

The second line contains integers c_1\ c_2\ \ldots\ c_n (1 \le c_i \le n) — the colors of the nodes.

The -th of next n-1 lines contains integers u_i, v_i (1 \le u_i, v_i \le n, u_i \neq v_i), representing the edge (u_i, v_i) of the tree. It is guaranteed that the given graph is a tree.

Output

Print a single integer — answer to the problem modulo .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the following pictures, we use blue for color , red for color , and yellow for color . The first example looks as follows:

The tree has a total of non-empty connected subgraphs:  of size , of size and of size , the latter in fact being the whole tree. All such subgraphs of sizes and have a majority color. For those of size only the subgraph induced by vertices and does not have a majority color (red and yellow both appear equally often in it). Therefore, there are 6 - 1 = 5 connected subgraphs with a majority color.

The second example looks as follows, and it has connected subgraphs with a majority color: