전구

Bajtazar에게는 1번부터 $n$번까지 번호가 붙은 전구 $n$개와 스위치 $m$개가 있다. 각 전구는 처음에 켜져 있거나 꺼져 있다. 각 스위치는 전구 한 쌍에 영향을 준다. 스위치를 누르면 두 전구의 상태가 반대로 바뀌는데, 두 전구가 같은 상태(둘 다 켜짐 또는 둘 다 꺼짐)일 때만 그렇다. 두 전구의 상태가 다르면 스위치를 눌러도 아무 일도 일어나지 않는다.

Bajtazar는 켜짐과 꺼짐으로 이루어진 전구 구성 중 도달할 수 있는 서로 다른 구성이 몇 개인지 알고 싶다. 스위치는 순서에 상관없이 원하는 만큼 누를 수 있고, 같은 스위치를 여러 번 써도 된다. 어떤 전구가 한 구성에서는 켜져 있고 다른 구성에서는 꺼져 있으면 두 구성은 다른 것이다. 답이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 줄에 두 정수 $n$과 $m$이 주어진다($1 \le n \le 200\,000$, $0 \le m \le 400\,000$). 두 번째 줄에는 공백으로 구분된 정수 $n$개 $c_i$($c_i \in \{0, 1\}$)가 주어진다. $c_i = 1$이면 $i$번 전구는 처음에 켜져 있고, $c_i = 0$이면 꺼져 있다.

이어지는 $m$개의 줄은 스위치를 하나씩 설명한다. $i$번째 줄에는 두 정수 $a_i$와 $b_i$($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 주어지며, 이는 $i$번째 스위치가 영향을 주는 전구의 번호이다. 서로 다른 두 스위치가 같은 전구 쌍에 영향을 주지 않는다. 즉 모든 $i \ne j$에 대해 $(a_i, b_i) \ne (a_j, b_j)$이고 $(a_i, b_i) \ne (b_j, a_j)$이다.

도달 가능한 전구 구성의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

예시에서 도달 가능한 최종 전구 상태는 10110, 00010, 00111, 10011이다.