Karma and Dharma Graph

Time limit1sMemory limit1024 MB

Summary

Count the colorings reachable from the initial coloring under the western rule (flip both endpoints of a same-colored edge) and the eastern rule (flip one endpoint), modulo 1000000007.

Level: Medium7 of 10
Topics: Graph, DFS, Math, Combinatorics
Solved: No attempts yet

Problem

A pilgrim keeps making a pilgrimage that seems like it will never end. Over repeated pilgrimages, the pilgrim learned that the regions in the western and eastern parts of the continent have different traditions. A clear example is how they color a karma and dharma graph, and the coloring methods differ between the two regions.

A karma and dharma graph assigns each vertex a color: black, which means karma, or white, which means dharma. Every city on the continent keeps one karma and dharma graph at its center to honor a god. From time to time, the cities hold a festival where they recolor the vertices of the graph, which strengthens their faith in the god.

Because of what the graph means, the vertices must be colored in a special way. Surprisingly, the western and eastern regions color the vertices differently.

In the western region, whenever two vertices joined by an edge have the same color, they recolor both vertices to the opposite color. This is the only way they color vertices.
In the eastern region, whenever two vertices joined by an edge have the same color, they recolor only one of the two vertices to the opposite color. This is the only way they color vertices.

The opposite of black is white, and the opposite of white is black.

Given a karma and dharma graph, count the number of distinct ways its vertices can be colored under the western method and under the eastern method.

Input

The first line contains two integers $N$ and $M$ , the number of vertices and the number of edges in the graph. The vertices are numbered from $1$ to $N$ .

The second line contains a string $C$ of 0 and 1 characters. If the $i$ -th character is 0, vertex $i$ is colored black. If it is 1, vertex $i$ is colored white.

Each of the next $M$ lines contains two natural numbers $x$ and $y$ ( $1 \leq x, y \leq N$ , $x \neq y$ ), the two vertices joined by an edge. The same pair of vertices does not appear more than once.

Output

Print two integers separated by a space: the number of ways to color the vertices under the western method, and the number of ways under the eastern method. Print each count modulo $1\ 000\ 000\ 007$ .

Examples2

Example 1
Input
```
2 1
11
1 2
```
Expected output
```
2 3
```
Example 2
Input
```
4 3
1000
1 2
2 3
3 4
```
Expected output
```
4 11
```