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

#define st first
#define nd second

typedef long long int lli;

const int MAXN = 200005;
const lli MOD = 1000000007;

int t[MAXN];

vector<int> v[MAXN];

int lab[MAXN];

lli pot(lli a, int n) {
    if (n == 0)
        return 1;
    
    if (n % 2 == 0)
        return pot((a*a)%MOD, n/2);
    else
        return (a * pot(a, n-1)) % MOD;
}

lli rev(lli a) {
    return pot(a, MOD-2);
}

lli fact[MAXN];

lli binom(lli n, lli k) {
//     printf("  binom %lld %lld\n", n, k);
    return (((fact[n] * rev(fact[k])) % MOD) * rev(fact[n-k])) % MOD;
}

bool found_conflict;

pair<pair<lli, lli>, pair<lli, lli>> sumuj(pair<pair<lli, lli>, pair<lli, lli>> a, pair<pair<lli, lli>, pair<lli, lli>> b) {
    return {{a.st.st+b.st.st, a.st.nd+b.st.nd}, {a.nd.st+b.nd.st, a.nd.nd+b.nd.nd}};
}

// {{n_1, n_2}, {s_n_1, s_n_2}}
pair<pair<lli, lli>, pair<lli, lli>> dfs(int x, int l) {
    lab[x] = l;
    
    int tmp[4];
    tmp[l] = 1;
    tmp[3-l] = 0;
    
    pair<pair<lli, lli>, pair<lli, lli>> res = {{tmp[1], tmp[2]}, {tmp[1]*t[x], tmp[2]*t[x]}};
    
    for (int a : v[x]) {
        if (lab[a] == l) {
//             return {{MAXN, 0}, {0, 0}};
            found_conflict = true;
        }
        
        if (lab[a] == 0)
            res = sumuj(res, dfs(a, 3-l));
    }
    
    return res;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    fact[0] = 1;
    for (int i=1; i<=n; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    for (int i=0; i<n; i++) {
        scanf("%d", &t[i]);
    }
    
    for (int i=0; i<m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    lli fin = 1;
    
    for (int i=0; i<n; i++) {
        if (lab[i] == 0) {
            found_conflict = false;
            auto r = dfs(i, 1);
            
            if (found_conflict) {
                fin = (fin * pot(2, r.st.st+r.st.nd-1)) % MOD;
//                 printf("full: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin);
            } else {
                fin = (fin * binom(r.st.st+r.st.nd, r.st.st + r.nd.nd - r.nd.st)) % MOD;
//                 printf("bicol: (%lld %lld), (%lld %lld), %lld\n", r.st.st, r.st.nd, r.nd.st, r.nd.nd, fin);
            }
            
//             printf(" %lld, %d\n", fin, found_conflict);
        }
    }
    
    printf("%lld\n", fin);
    
    return 0;
}