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
#include <bits/stdc++.h>
#define fi first
#define sc second
#define pb push_back
#define rep(i,p,k) for(int i=(p);i<(k);++i)
#define forn(i,p,k) for(int i=(p);i<=(k);++i)
#define forr(i,k,p) for(int i=(k)-1;i>=(p);--i)
#define each(a,b) for(auto&a:b)
#define all(v)  begin(v), end(v)
#define RET(smth)   return void(cout<<(smth)<<'\n');
#define sz(v) (int)v.size()
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using Vi = vector<int>;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) ;
#endif

constexpr int P = 1e9+7;

ll mul(ll a, ll b) {
    return a*b%P;
}

ll fastpow(ll x, int n) {
    ll r = 1;
    for(;n;n/=2) {
        if(n&1) r = mul(r,x);
        x = mul(x,x);
    }
    return r;
}

int main() {
#ifndef DEBUG
    cin.tie(0) -> sync_with_stdio(0);
#endif
    int n,m; cin >> n >> m;
    vector<Vi> W(n);
    vector<ll> fac(n+1),inv(n+1);
    fac[0] = 1;
    inv[0] = inv[1] = 1;
    forn(i,1,n) fac[i] = mul(i, fac[i-1]);
    forn(i,2,n) inv[i] = mul(P/i, P - inv[P%i]);
    forn(i,2,n) inv[i] = mul(inv[i],inv[i-1]);
    auto cnk = [&](int n, int k) {return mul(fac[n],mul(inv[k],inv[n-k]));};
    Vi col(n);
    for(auto&v:col) cin >> v;
    while(m--) {
        int a,b; cin >> a >> b; --a; --b;
        W[a].push_back(b);
        W[b].push_back(a);
    }
    long long res = 1;
    Vi vis(n, 0);
    auto dfs = [&](int w, int & cnt, bool & bipar, int c, auto && self) -> int {
        vis[w] = c;
        if((c^2) == col[w]) cnt++;
        int r = 1;
        for(auto v : W[w]) {
            if(!vis[v]) r += self(v,cnt,bipar,c^1,self);
            if(vis[w] == vis[v]) bipar = false;
        }
        return r;
    };
    rep(i,0,n) if(!vis[i]) {
        int cnt{};
        bool bipar = true;
        int s = dfs(i,cnt,bipar,2,dfs);
        if(!bipar) res = mul(res, fastpow(2,s-1));
        else res = mul(res, cnk(s,cnt));
    }
    cout << res << '\n';
    return 0;
}