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
127
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int mod = 1e9+7;

int mul(int a, int b){
    return (a*b)%mod;
}

void add(int &a, int b){
    a += b;
    if (a >= mod) a-=mod;
}

int power(int a, int b){
    if (!b) return 1ll;
    int k = power(a, b/2);
    k = mul(k, k);
    if (b&1) k = mul(k, a);
    return k;
}

void solve(){
    int n, m; cin >> n >> m;
    vector<int>a(n+1);
    for (int i = 1; i<=n; i++) cin >> a[i];
    vector<vector<int>>g(n+1);
    for (int i = 0; i<m; i++){
        int _a, b; cin >> _a >> b;
        g[_a].emplace_back(b);
        g[b].emplace_back(_a);
    }
    vector<bool>vis(n+1), color(n+1);
    bool any = 0;
    vector<int>fix;
    function<bool(int)>dfs = [&](int v){
        vis[v] = 1;
        fix.emplace_back(v);
        bool ret = 1;
        for (auto x: g[v]){
            if (a[v] == a[x]) any = 1;
            if (vis[x]){
                if (color[x] == color[v]) ret = 0;
            } else {
                color[x] = color[v]^1;
                if (!dfs(x)) ret = 0;
            }
        }
        return ret;
    };
    int ans = 1;
    vector<int>f(n+1, 1), inv(n+1, 1);
    for (int i = 1; i<=n; i++){
        f[i] = mul(f[i-1], i);
        inv[i] = mul(inv[i-1], power(i, mod-2));
    } 
    auto nck = [&](int N, int K){
        if (N < 0 || K < 0 || N < K) return 0ll;
        return mul(f[N], mul(inv[K], inv[N-K]));
    };  
    for (int i = 1; i<=n; i++){
        if (!vis[i]){
            any = 0;
            fix.clear();
            auto t = dfs(i);
            debug(any, (int)t, fix);
            if (!any) continue;
            if (!t) {
                for (int j = 0; j<(int)fix.size()-1; j++) ans = mul(ans, 2);
                continue;
            }
            array<int, 2>cnt = {0, 0};
            array<int, 2>cnt2 = {0, 0};
            for (auto v: fix){
                debug(v, (int)color[v]);
                if (a[v]) cnt[color[v]]++;
                cnt2[color[v]]++;
            }
            int diff = cnt[0]-cnt[1];
            int curr = 0;
            debug(diff);
            for (int a = 0, b = diff; a <= cnt2[1] && b <= cnt2[0]; a++, b++){
                debug(b, a);
                add(curr, mul(nck(cnt2[0], b), nck(cnt2[1], a)));                
            }
            ans = mul(ans, curr);
        }
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}