Bajtazar possède $n$ ampoules numérotées de $1$ à $n$ et $m$ interrupteurs. Chaque ampoule est initialement allumée ou éteinte. Chaque interrupteur agit sur une paire d'ampoules donnée. L'actionner inverse l'état des deux ampoules, mais seulement si elles sont dans le même état (toutes deux allumées ou toutes deux éteintes). Dans le cas contraire, l'actionnement de l'interrupteur n'a aucun effet.

Bajtazar se demande combien de configurations différentes d'ampoules allumées et éteintes il peut atteindre en utilisant les interrupteurs un nombre illimité de fois, dans n'importe quel ordre, et potentiellement en utilisant certains interrupteurs plusieurs fois. Deux configurations sont considérées comme différentes si au moins une ampoule est allumée dans l'une et éteinte dans l'autre. Comme le résultat peut être très grand, il suffit de donner le reste de sa division par $10^9 + 7$.

Entrée

La première ligne de l'entrée contient deux entiers $n$ et $m$ ($1 \le n \le 200\,000$ ; $0 \le m \le 400\,000$), représentant respectivement le nombre d'ampoules et le nombre d'interrupteurs.

La deuxième ligne de l'entrée contient $n$ nombres $c_i$ ($c_i \in \{0, 1\}$) séparés par des espaces. Si $c_i = 1$, la $i$-ème ampoule est initialement allumée. Sinon (si $c_i = 0$), la $i$-ème ampoule est initialement éteinte.

Les $m$ lignes suivantes contiennent les descriptions des interrupteurs ; la $i$-ème de ces lignes contient deux entiers $a_i$ et $b_i$ ($1 \le a_i, b_i \le n$ ; $a_i \neq b_i$) – les numéros des ampoules sur lesquelles agit le $i$-ème interrupteur.

Vous pouvez supposer que les interrupteurs agissent sur des paires d'ampoules non ordonnées distinctes. Plus formellement, pour chaque paire d'indices distincts $i, j$ compris entre $1$ et $m$ inclus, on a $(a_i, b_i) \neq (a_j, b_j)$ et $(a_i, b_i) \neq (b_j, a_j)$.

Sortie

La première et unique ligne de la sortie doit contenir le reste de la division par $10^9 + 7$ du nombre de configurations atteignables d'ampoules allumées et éteintes.

Exemples

Entrée 1

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

Sortie 1

4

Remarque 1

Les états finaux atteignables des ampoules sont 10110, 00010, 00111 et 10011.