1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

#define LOCAL false

const int MAX_V = 2e5 + 7;
const int MAX_E = 4e5 + 7;
int V, E;

bool toggled[MAX_V];
vector<int> graph[MAX_V];
bool state[MAX_V];
bool vis[MAX_V];

int truecnt, falsecnt;
int truecnt2, falsecnt2;
bool not2col;
void dfs(int v, bool curstate = true) {
    vis[v] = true;
    state[v] = curstate;
    if (curstate) {
        truecnt++;
        if (toggled[v]) truecnt2++;
    } else {
        falsecnt++;
        if (toggled[v]) falsecnt2++;
    }
    for (int to: graph[v]) {
        if (!vis[to]) dfs(to, !curstate);
        else if (state[to] == curstate) not2col = true;
    }
}

int pow2mod[MAX_V];
int factmod[MAX_V];

int fastpow(int n, int p) {
    int ans = 1;
    while (p) {
        if (p&1) ans = ((ll)ans*n)%MOD;
        p >>= 1;
        n = ((ll)n*n)%MOD;
    }
    return ans;
}

int choose(int n, int k) {
    int nom = factmod[n];
    int denom = ((ll)factmod[k]*factmod[n-k])%MOD;
    // cout << nom << ' ' << denom << "???\n";
    return ((ll)nom*fastpow(denom, MOD-2))%MOD;
}

int calc2col(int N, int n, int k) {
    return choose(N, n-k);
    // int ans = 0;
    // rep(x, n-k+1) {
    //     int add = ((ll)choose(n, x+k)*choose(N-n, x))%MOD;
    //     ans = (ans+add)%MOD;
    // }
    // return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (LOCAL) {
        ignore=freopen("io/in", "r", stdin);
        ignore=freopen("io/out", "w", stdout);
    }


    cin >> V >> E;
    rep1(v, V) cin >> toggled[v];
    int v1, v2;
    rep(i, E) {
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }

    pow2mod[0] = 1;
    rep1(p, V) pow2mod[p] = (2*pow2mod[p-1])%MOD;

    factmod[0] = 1;
    rep1(f, V) factmod[f] = ((ll)f*factmod[f-1])%MOD;

    int ans = 1;
    rep1(v, V) if (!vis[v]) {
        truecnt = 0; falsecnt = 0;
        truecnt2 = 0; falsecnt2 = 0;
        not2col = false;
        dfs(v);
        // cout << truecnt << ' ' << falsecnt << " .\n";
        // cout << truecnt2 << ' ' << falsecnt2 << " .\n";
        int N = truecnt+falsecnt;
        if (not2col) ans = ((ll)ans*pow2mod[N-1])%MOD;
        else {
            int mn = min(truecnt2, falsecnt2);
            truecnt2 -= mn;
            falsecnt2 -= mn;
            int n, k;
            if (truecnt2 > falsecnt2) {
                n = truecnt;
                k = truecnt2;
            } else {
                n = falsecnt;
                k = falsecnt2;
            }
            // cout << N << ' ' << n << ' ' << k << " -> " << calc2col(N, n, k) << "!!\n";
            ans = ((ll)ans*calc2col(N, n, k))%MOD;
        }
    }
    cout << ans << '\n';

    return 0;
}