Bajtazar sở hữu $n$ bóng đèn được đánh số từ $1$ đến $n$ và $m$ công tắc. Mỗi bóng đèn ban đầu có thể đang bật hoặc tắt. Mỗi công tắc tác động lên một cặp bóng đèn nhất định. Việc sử dụng công tắc sẽ thay đổi trạng thái của cả hai bóng đèn đó sang trạng thái ngược lại, nhưng chỉ với điều kiện là cả hai bóng đèn đang ở cùng một trạng thái – cả hai cùng bật hoặc cả hai cùng tắt. Nếu không, việc nhấn công tắc sẽ không có tác dụng gì.

Bajtazar muốn biết có bao nhiêu cấu hình khác nhau của các bóng đèn đang bật và tắt mà anh ấy có thể đạt được, bằng cách sử dụng các công tắc tùy ý nhiều lần theo bất kỳ thứ tự nào, và có thể sử dụng một số công tắc nhiều lần. Hai cấu hình được coi là khác nhau nếu có ít nhất một bóng đèn đang bật ở cấu hình này nhưng lại tắt ở cấu hình kia. Vì kết quả có thể rất lớn, bạn chỉ cần đưa ra phần dư của nó khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($1 \le n \le 200\,000$; $0 \le m \le 400\,000$), lần lượt là số lượng bóng đèn và số lượng công tắc.

Dòng thứ hai chứa $n$ số $c_i$ ($c_i \in \{0, 1\}$) cách nhau bởi các khoảng trắng. Nếu $c_i = 1$, bóng đèn thứ $i$ ban đầu đang bật. Ngược lại (nếu $c_i = 0$), bóng đèn thứ $i$ ban đầu đang tắt.

Trong $m$ dòng tiếp theo là mô tả các công tắc; dòng thứ $i$ trong số này chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i, b_i \le n$; $a_i \neq b_i$) – là số hiệu của các bóng đèn mà công tắc thứ $i$ tác động lên.

Bạn có thể giả định rằng các công tắc tác động lên các cặp bóng đèn không có thứ tự khác nhau. Cụ thể hơn, với mọi cặp chỉ số khác nhau $i, j$ từ $1$ đến $m$, ta có $(a_i, b_i) \neq (a_j, b_j)$ và $(a_i, b_i) \neq (b_j, a_j)$.

Dữ liệu ra

Dòng đầu tiên và duy nhất của dữ liệu ra phải chứa phần dư của số lượng các cấu hình bóng đèn có thể đạt được khi chia cho $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4

Ghi chú

Giải thích ví dụ: Các trạng thái cuối cùng có thể đạt được của các bóng đèn là 10110, 00010, 00111 và 10011.