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
#include <iostream>
#include <map>
#include <vector>
#include <bitset>

using namespace std;

const int MAX_N = 200'007;
const long long mod = 1'000'000'007;

vector<int>adj[MAX_N];
int col[MAX_N], state[MAX_N];

void dfs(int x, vector<int>&v) {
    v.push_back(x);
    for(int y : adj[x]) {
        if(col[y] == -1) {
            col[y] = 1 - col[x];
            dfs(y, v);
        }
    }
}

long long fact[MAX_N];

long long bpow(long long x, long long exp) {
    if(exp == 0)
        return 1;
    long long r = bpow(x, exp / 2);
    r = r * r % mod;
    if(exp % 2 == 1)
        r = r * x % mod;
    return r;
}

long long choose(int n, int k) {
    long long ans = fact[n] * bpow(fact[k], mod - 2) % mod;
    return ans * bpow(fact[n - k], mod - 2) % mod;
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < MAX_N; i++)
        fact[i] = fact[i - 1] * i % mod;
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> state[i];
        col[i] = -1;
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    long long result = 1;
    for(int i = 0; i < n; i++) {
        if(col[i] == -1) {
            vector<int>v;
            col[i] = 0;
            dfs(i, v);
            
            bool bipart = true;
            for(int x : v) {
                for(int y : adj[x]) {
                    if(col[x] == col[y]) {
                        bipart = false;
                    }
                }
            }
            
            if(!bipart) {
                result = result * bpow(2, v.size() - 1) % mod;
            } else {
              //  cout << "bipart\n";
                int left = 0, right = 0, lone = 0, rone = 0;
                for(int x : v) {
                    if(col[x] == 0) {
                        left++;
                        lone += state[x];
                    } else {
                        right++;
                        rone += state[x];
                    }
                }
                
//                 cout << "left = " << left << " right = " << right << "\n";
//                 cout << "lone = " << lone << ", rone = " << rone << "\n";
                
                long long local = 0;
                
                for(int i = -min(left - lone, right - rone); i <= min(lone, rone); i++) {
                    local = (local + choose(left, lone - i) * choose(right, rone - i)) % mod;
                }
                
//                 cout << "local = " << local << "\n";
                
                result = result * local % mod;
            }
        }
    }
    
    cout << result << "\n";
}