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
#include<bits/stdc++.h>
using namespace std;

const int n_max = 2*1e5+7;
const long long mod = 1e9+7;

long long factorial[n_max];
int state[n_max];
int zone[n_max];
vector<int> graph[n_max];
int blocked[n_max]; // 0 - yes, 1 - no
int bigraph[n_max]; // 0 - yes, 1 - no
int state_of_bigraph[n_max]; 
int zone_size[n_max];
int zone_size_bigraph[2][n_max];
int zone_one[2][n_max];

void init(int n){
    factorial[0] = 1;
    for(long long i = 1; i <= n; i++){
        factorial[i] = (i * factorial[i-1])%mod;
    }
}

long long fast_pot(long long a, long long stopien){
    if(stopien == 0){
        return 1;
    }
    if(stopien%2 == 0){
        return fast_pot((a*a)%mod, stopien/2);
    }else{
        return (fast_pot((a*a)%mod, stopien/2)*a)%mod;
    }
}


long long newton_symbol(long long n, long long k){
    return (((factorial[n] * fast_pot(factorial[k], mod - 2))%mod) * fast_pot(factorial[n-k], mod - 2))%mod;
}

void dfs(int v, int p, int zone_number, int nr_bigraph = 1){
    state_of_bigraph[v] = nr_bigraph;
    zone[v] = zone_number;
    zone_size[zone_number]++;
    zone_size_bigraph[nr_bigraph][zone_number]++;
    if(state[v] == 1){
        zone_one[nr_bigraph][zone_number]++;
    }
    for(auto u: graph[v]){
        if(u != p){
            if(state[v] == state[u]){
                blocked[zone_number] = 1;
            }
            if(zone[u] == 0){
                dfs(u, v, zone_number, (nr_bigraph + 1)%2);
            }else{
                if(state_of_bigraph[v] == state_of_bigraph[u]){
                    bigraph[zone_number] = 1;
                }
            }

        }
    }

}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    init(n);
    //cout << newton_symbol(2, 1) << " " << newton_symbol(n, m);
    for(int i = 1; i <= n; i++){
        cin >> state[i];
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    long long ans = 1;
    for(int i = 1; i <= n; i++){
        if(zone[i] == 0){
            dfs(i, 0, i);
            if(blocked[i] == 0){
                continue;
            }
            if(bigraph[i] == 0){
                // Graf jest dwudzielny...
                int min_one = min(zone_one[0][i], zone_one[1][i]);
                zone_one[0][i] -= min_one;
                zone_one[1][i] -= min_one;
                long long ans_tmp = 0;
                while(zone_one[0][i] <= zone_size_bigraph[0][i] and zone_one[1][i] <= zone_size_bigraph[1][i]){
                    ans_tmp = (ans_tmp + newton_symbol(zone_size_bigraph[0][i], zone_one[0][i]) * newton_symbol(zone_size_bigraph[1][i], zone_one[1][i]))%mod;
                    zone_one[0][i]++;
                    zone_one[1][i]++;
                }
                ans = (ans * ans_tmp)%mod;
            }else{
                // Graf nie jest dwudzielny
                long long ans_tmp = 0;
                for(int j = 0; j <= zone_size[i]; j += 2){
                    ans_tmp = (ans_tmp + newton_symbol(zone_size[i], j))%mod;
                }
                ans = (ans * ans_tmp)%mod;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}