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
124
125
126
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define pb emplace_back
#define ins insert
#define mp make_pair
#define ssize(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pld pair <ld, ld>
#define st first
#define nd second

using namespace std;
using ll = int_fast64_t;
// using lll = __int128_t;
using ld = long double;
const int oo = 1e9 + 7;
const ll ool = 1e18;
const int mod = 1e9 + 7;

struct DSU{
    vector <int> rep, sz;
    DSU(int n){
        rep.resize(n);
        sz.assign(n, 1);
        iota(all(rep), 0);
    }
    int find(int x){
        if(rep[x] == x) return x;
        return rep[x] = find(rep[x]);
    }
    int get(int x){
        return sz[find(x)];
    }
    bool same(int a, int b){
        return find(a) == find(b);
    }
    void un(int a, int b){
        sz[find(a)] += sz[find(b)];
        rep[find(b)] = find(a);
    }
};
void solve(){
    int n, m; cin >> n >> m;
    vector <int> tab(n);
    for(auto &i: tab) cin >> i;
    vector <vector<int>> g(n);
    DSU T(n);
    while(m --){
        int a, b; cin >> a >> b;
        -- a; -- b;
        g[a].pb(b);
        g[b].pb(a);
        if(!T.same(a, b)) T.un(a, b);
    }
    vector <vector<int>> wh(n);
    for(int i = 0; i < n; i ++) wh[T.find(i)].pb(i);
    vector <bool> is(n), vis(n), col(n);
    function<void(int, bool)> dfs = [&](int v, bool x){
        vis[v] = 1;
        col[v] = x;
        for(auto u: g[v]){
            if(!vis[u]) dfs(u, !x);
        }
    };
    auto fp = [&](ll a, ll b){
        ll r = 1;
        while(b){
            if(b & 1) r = (r * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return r;
    };
    vector <ll> fact(n + 3, 1);
    for(ll i = 1; i <= n; i ++) fact[i] = (fact[i - 1] * i) % mod;
    auto c = [&](ll n, ll k){
        return (fact[n] * fp((fact[k] * fact[n - k]) % mod, mod - 2)) % mod;
    };
    ll ans = 1;
    for(int i = 0; i < n; i ++){
        int rn = T.find(i);
        if(is[rn] || T.get(rn) == 1) continue;
        is[rn] = 1;
        dfs(wh[rn][0], 0);
        bool bi = 1;
        for(auto v: wh[rn]){
            for(auto u: g[v]){
                if(col[v] == col[u]) bi = 0;
            }
        }
        if(!bi){
            ans = (ans * fp(2, T.get(rn) - 1)) % mod;
            continue;
        }
        pii a = mp(0, 0), b = mp(0, 0);
        for(auto v: wh[rn]){
            if(col[v]){
                ++ a.st;
                if(tab[v]) ++ a.nd;
            }
            else{
                ++ b.st;
                if(tab[v]) ++ b.nd;
            }
        }
        if(a.nd > b.nd) swap(a, b);
        ll curr = 0;
        for(int j = 0; j <= min(a.st, b.st); j ++){
            if(j > a.st || j + b.nd - a.nd > b.st) continue;
            curr = (curr + (c(a.st, j) * c(b.st, j + b.nd - a.nd)) % mod) % mod;
        }
        ans = (ans * curr) % mod;
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; t = 1;
    // cin >> t;
    while(t --) solve();
    return 0;
}