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
#include <bits/stdc++.h>
#define dbg(x) " [" << #x << ": " << (x) << "] "
using namespace std;
using ll = long long;
template<typename A, typename B>
ostream& operator<<(ostream& out, const pair<A,B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c) {
    out << "{";
    for(auto it = c.begin(); it != c.end(); it++) {
        if(it != c.begin()) out << ", ";
        out << *it;
    }
    return out << "}";
}

const int mod = 1e9 + 7;

vector<int> col;
vector<vector<int>> g, comp;
vector<int> u, bipart, bipart_col, comp_cnt;
void dfs(int v, int c, int c2) {
    u[v] = c2;
    comp[c].push_back(v);
    comp_cnt[c]++;
    for(int to : g[v]) {
        if(col[to] == col[v]) bipart_col[c] = 0;
        if(u[to] == c2) bipart[c] = 0;
        if(u[to]) continue;
        dfs(to, c, c2 ^ 2);
    }
}

ll bp(ll a, ll b) {
    ll r = 1;
    while(b) {
        if(b & 1) r = r * a % mod;
        b /= 2;
        a = a * a % mod;
    }
    return r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    col.resize(n);
    g.resize(n);
    u.resize(n);
    comp.resize(n);
    comp_cnt.resize(n);
    bipart_col.assign(n, 1);
    bipart.assign(n, 1);
    for(int& i : col) cin >> i;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<ll> pw2(n + 1), f(n + 1), invf(n + 1);
    pw2[0] = 1;
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        pw2[i] = 2 * pw2[i - 1] % mod;
        f[i] = f[i - 1] * i % mod;
    }
    invf.back() = bp(f.back(), mod - 2);
    for(int i = n - 1; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }

    auto bin = [&](int n, int k) {
        return f[n] * invf[k] % mod * invf[n - k] % mod;
    };

    int cnt = 0;
    ll ans = 1;
    for(int i = 0; i < n; i++) {
        if(!u[i]) {
            dfs(i, cnt, 1);
            if(!bipart_col[cnt]) {
                int sz = comp_cnt[cnt];
                if(bipart[cnt]) {
                    int a = 0, b = 0, diff = 0;
                    for(int x : comp[cnt]) {
                        if(u[x] == 1) {
                            diff += col[x];
                            a++;
                        } else {
                            diff -= col[x];
                            b++;
                        }
                    }
                    ll sum = 0;
                    for(int x = 0; x <= a; x++) {
                        int y = x - diff;
                        if(y < 0 || y > b) continue;
                        sum = (sum + bin(a, x) * bin(b, y)) % mod;
                    }
                    ans = ans * sum % mod;
                } else {
                    ans = ans * pw2[sz - 1] % mod;
                }
            }
            cnt++;
        }
    }
    cout << ans << endl;

    return 0;
}