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
#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;

const int MOD = 1e9 + 7;

int n, m;
vector<bool> bulbs;
vector<unordered_set<int>> adjacency;
vector<bool> visited;

long long twoToPower(int power) {
    long long result = 1LL;
    long long base = 2LL;
    while (power > 0) {
        if (power % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        power /= 2;
    }

    return result;
}

long long binomialCoefficient(int above, int below) {
    vector<long long> inv(below + 1);
    inv[0] = 1;
    if (below + 1 >= 2)
        inv[1] = 1;

    for (int i = 2; i <= below; i++) {
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    }

    long long result = 1LL;

    for (int i = 2; i <= below; i++) {
        result = ((result % MOD) * (inv[i] % MOD)) % MOD;
    }

    for (int i = above; i >= (above - below + 1); i--) {
        result = ((result % MOD) * (i % MOD)) % MOD;
    }
    return result;
}

long long bfs(int start) {
    queue<int> queue;
    queue.push(start);
    visited[start] = true;
    int size = 0;
    vector<bool> parity(n);
    bool hasOddCycle = false;
    int enabled = 0;

    while (!queue.empty()) {
        int v = queue.front();
        queue.pop();
        size++;
        enabled += bulbs[v] == parity[v] ? 0 : 1;

        for (int u : adjacency[v]) {
            if (visited[u]) {
                if (parity[u] == parity[v]) {
                    hasOddCycle = true;
                }
            } else {
                visited[u] = true;
                queue.push(u);
                parity[u] = !parity[v];
            }
        }
    }
    if (hasOddCycle) {
        return twoToPower(size - 1);
    } else {
        return binomialCoefficient(size, enabled);
    }
}

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

    cin >> n >> m;
    adjacency.resize(n);
    visited.resize(n);

    int bulb;
    for (int i = 0; i < n; i++) {
        cin >> bulb;
        bulbs.push_back(bulb > 0);
    }

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        adjacency[a - 1].insert(b - 1);
        adjacency[b - 1].insert(a - 1);
    }

    long long result = 1LL;
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            result = (result * bfs(i)) % MOD;
        }
    }

    cout << result << endl;
}