18346번 - 업과 격의 그래프 서브태스크

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

업과 격의 그래프란 그래프의 각 정점에 업을 의미하는 색인 검은색 혹은 격을 의미하는 색인 하얀색을 칠해둔 것인데, 대륙의 모든 도시는 신을 기리기 위한 의미로 업과 격의 그래프 하나를 도시 중앙에 두고 있다. 그리고 가끔 그래프의 정점들을 새롭게 칠하는 축제를 열면서, 신에 대한 믿음을 더욱 공고히 한다.

업과 격의 그래프에 담긴 의미 때문에, 정점을 칠하는 방법은 특별해야 한다. 그리고 놀랍게도, 정점을 칠하는 방법은 대륙 서부와 대륙 동부가 서로 다르다.

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

여기서 당연하게도 검은색의 반대 색은 하얀색이고, 하얀색의 반대 색은 검은색이다.

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

첫 번째 줄에, 주어지는 그래프의 정점 개수와 간선 개수를 나타내는 정수 $N$과 $M$이 주어진다. 그래프의 각 정점에는 $1$에서 $N$까지의 번호가 붙는다.

두 번째 줄에, 각 정점에 칠해진 색을 의미하는 문자열 $C$가 주어진다. 문자열은 0 또는 1로 이루어져 있으며, $i$번째 문자가 0이면 $i$번 정점이 검은색으로 칠해져 있고, 1이면 $i$번 정점이 하얀색으로 칠해져 있다.

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

첫 번째 줄에, 대륙 서부의 방식과 대륙 동부의 방식으로 그래프의 정점을 칠할 때 그래프의 정점들이 칠해질 수 있는 서로 다른 방법의 개수를 공백 하나로 구분하여 출력한다. 칠하는 방법이 매우 많을 수 있으므로, 둘 다 $1\ 000\ 000\ 007$로 나눈 나머지를 출력하도록 한다.

• $1 \leq N \leq 20$
• $1 \leq M \leq 40$

• $1 \leq N \leq 10^5$
• $M = N-1$
• 모든 정점이 간선을 통해 연결되어 있다.

즉, 트리 형태의 그래프가 주어진다.

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 2 \times 10^5$