업과 격의 그래프

순례자는 영원히 끝나지 않을 것만 같은 순례를 계속하고 있다. 반복되는 순례에서 순례자는 대륙 서부 지역과 대륙 동부 지역의 전통이 서로 다르다는 것을 알게 되었다. 대표적인 예가 업과 격의 그래프를 칠하는 방법이며, 두 지역의 방법이 서로 다르다.

업과 격의 그래프는 각 정점에 업을 뜻하는 검은색 또는 격을 뜻하는 하얀색을 칠한 것이다. 대륙의 모든 도시는 신을 기리기 위해 도시 중앙에 업과 격의 그래프 하나를 둔다. 도시들은 가끔 축제를 열어 그래프의 정점을 새로 칠하고, 이를 통해 신에 대한 믿음을 다진다.

그래프가 가진 의미 때문에 정점을 칠하는 방법은 특별해야 한다. 놀랍게도 대륙 서부와 대륙 동부는 정점을 칠하는 방법이 다르다.

• 대륙 서부에서는 간선으로 연결된 두 정점의 색이 같으면, 두 정점의 색을 모두 반대 색으로 바꾼다. 이 방식으로만 정점을 칠한다.
• 대륙 동부에서는 간선으로 연결된 두 정점의 색이 같으면, 두 정점 중 한 정점의 색만 반대 색으로 바꾼다. 이 방식으로만 정점을 칠한다.

검은색의 반대 색은 하얀색이고, 하얀색의 반대 색은 검은색이다.

업과 격의 그래프가 주어질 때, 대륙 서부의 방식과 대륙 동부의 방식 각각에 대해 정점들을 칠할 수 있는 서로 다른 방법이 몇 가지인지 구하라.

첫 번째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. 그래프의 각 정점에는 $1$부터 $N$까지의 번호가 붙는다.

두 번째 줄에 각 정점의 색을 나타내는 문자열 $C$가 주어진다. $i$번째 문자가 0이면 $i$번 정점은 검은색이고, 1이면 하얀색이다.

다음 $M$개의 줄에는 간선으로 연결된 두 정점을 나타내는 자연수 $x$, $y$ ($1 \leq x, y \leq N$, $x \neq y$)가 한 줄에 하나씩 주어진다. 같은 두 정점을 잇는 간선은 여러 번 주어지지 않는다.

대륙 서부의 방식과 대륙 동부의 방식으로 정점을 칠하는 방법의 수를 공백으로 구분하여 한 줄에 출력한다. 두 값 모두 $1\ 000\ 000\ 007$로 나눈 나머지를 출력한다.