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$번째 줄에는 $i$번째 스위치가 영향을 미치는 두 전구의 번호 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)가 주어집니다.

스위치들은 서로 다른 순서 없는 전구 쌍에 영향을 미친다고 가정할 수 있습니다. 더 형식적으로 말하면, $1$부터 $m$ 사이의 서로 다른 모든 인덱스 쌍 $i, j$에 대하여 $(a_i, b_i) \neq (a_j, b_j)$이고 $(a_i, b_i) \neq (b_j, a_j)$입니다.

출력

첫 번째 줄에 도달 가능한 전구의 상태 조합의 수를 $10^9 + 7$로 나눈 나머지를 출력합니다.

예제

입력 1

5 4
1 0 1 1 0
1 3
5 3
4 2
1 5

출력 1

4

참고

예제 설명: 도달 가능한 전구의 최종 상태는 10110, 00010, 00111, 10011입니다.