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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MOD = 1000000007;

long long power(long long b, int e) {
    if (e == 0)
        return 1;
    long long half = power(b, e/2);
    half = (half * half) % MOD;
    if (e%2)
        return (b * half) % MOD;
    else
        return half;
}

long long inv(long long x) {
    return power(x, MOD-2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<bool> B(n);
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        B[i] = (x==1);
    }

    vector<vector<int>> G(n);
    for (int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        G[x-1].push_back(y-1);
        G[y-1].push_back(x-1);
    }

    // prepare factorial buffer
    vector<long long> Fact(n+1), InvFact(n+1);
    Fact[0] = Fact[1] = InvFact[0] = InvFact[1] = 1;
    for (int i=2; i<=n; i++) {
        Fact[i] = (Fact[i-1] * i) % MOD;
        InvFact[i] = inv(Fact[i]);
    }
    auto binom = [&](int n, int k) -> long long {
        return (((Fact[n] * InvFact[k]) % MOD) * InvFact[n-k]) % MOD;
    };

    vector<int> Col(n, -1);
    long long result = 1;
    for (int comp_root=0; comp_root<n; comp_root++)
        if (Col[comp_root] == -1) {
            // 2-coloring
            queue<int>Q;
            bool bipartite = true;
            Col[comp_root] = 0;
            int cntAll[2] = {1, 0};
            int cntLit[2] = {int(B[comp_root]), 0};
            Q.push(comp_root);
            while (!Q.empty()) {
                int v = Q.front();
                Q.pop();
                for (int nei : G[v])
                    if (Col[nei] == -1) {
                        Col[nei] = 1-Col[v];
                        cntAll[Col[nei]]++;
                        cntLit[Col[nei]]+=int(B[nei]);
                        Q.push(nei);
                    }
                    else if (Col[nei] == Col[v])
                        bipartite = false;
            }

            // if component is bipartite
            if (bipartite) {
                long long local_result = 0;
                int delta = cntLit[0]-cntLit[1];
                if (delta<0) {
                    delta = -delta;
                    swap(cntAll[0], cntAll[1]);
                }
                for (int l=delta,r=0; l<=cntAll[0] && r<=cntAll[1]; l++,r++)
                    local_result = (local_result + binom(cntAll[0], l) * binom(cntAll[1], r)) % MOD;
                result = (result * local_result) % MOD;
            }

            // if it has an odd cycle
            else
                result = (result * power(2, cntAll[0]+cntAll[1]-1)) % MOD;
        }

    cout << result << '\n';
    return 0;
}