Colorful Sets

You are given an undirected graph with N nodes and M edges, along with an array of N integers representing the color of each node. A set of nodes is called a colorful set if no two nodes in the set share the same color. Notice that the graph structure given by the edges does not affect the counting for this problem. Your task is to calculate the number of colorful sets modulo $$10^9+7$$.

Formally, let (k) be the number of unique colors among the nodes. Since each unique color can either be chosen or not chosen independently, the number of colorful sets is given by:

Output the result as specified.

inputFormat

Input is given via standard input (stdin). The first line contains two integers (N) and (M): the number of nodes and the number of edges, respectively. The second line contains (N) integers representing the colors of the nodes. Each of the following (M) lines contains two integers (u) and (v) indicating there is an edge between node (u) and node (v). Note that the edges do not affect the result.

outputFormat

Output the number of colorful sets modulo $$10^9+7$$ to standard output (stdout).## sample

4 3
1 2 2 3
1 2
2 3
3 4

8