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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int modul = 1000 * 1000 * 1000 + 7;

vector<int> pow2memo(1, 1);
int pow2(int exp) {
    while ((int)size(pow2memo) <= exp) {
        pow2memo.push_back((2 * pow2memo.back()) % modul);
    }
    return pow2memo[exp];
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> z(n);
    for (int i = 0; i < n; i++) {
        cin >> z[i];
    }
    vector<array<int, 2>> s;
    s.reserve(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        s.push_back({u, v});
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> sg(n);
    vector<int> prev(n, -1);
    vector<vector<int>> members(n);
    vector<bool> bp;
    int nr = 0;
    for (int i = 0; i < n; i++) {
        if (sg[i]) continue;
        nr = abs(nr);
        sg[i] = ++nr;
        vector<int> st;
        st.push_back(i);
        bp.push_back(true);
        while (st.size()) {
            int next = st.back();
            nr = sg[next];
            members[abs(nr) - 1].push_back(next);
            st.pop_back();
            for (int neigh : g[next]) {
                if (sg[neigh]) {
                    if (sg[neigh] == nr) {
                        bp.back() = false;
                    }
                } else {
                    sg[neigh] = -nr;
                    prev[neigh] = next;
                    st.push_back(neigh);
                }
            }
        }
    }
    int res = 1;
// for (auto [u, v] : s) cerr << u << '-' << v << ' '; cerr << endl;
    for (int i = 0; i < n; i++) {
// cerr << i << endl;
        int ix = abs(sg[i]) - 1;
        if (members[ix].size()) {
// cerr << ix << " of size " << members[ix].size() << endl;
            if (!bp[ix]) {
// cerr << "not bp" << endl;
                res *= pow2(size(members[ix]) - 1);
                res %= modul;
// cerr << res << endl;
            } else {
// cerr << "bp" << endl;
                unordered_map<int, int> remap;
                int nix = 0;
                for (int member : members[ix]) {
                    remap[member] = nix++;
                }
// for (auto &it : remap) {
    // cerr << it.first << " -> " << it.second << endl;
// }
                string zz;
                zz.reserve(nix);
                for (int member : members[ix]) {
                    zz.push_back('0' + z[member]);
                }
                vector<array<int, 2>> ss;
                for (auto [u, v] : s) {
                    if ((abs(sg[u]) == abs(sg[i])) && (abs(sg[i]) == abs(sg[v]))) {
                        ss.push_back({remap[u], remap[v]});
// cerr << u << '-' << v << " becomes " << remap[u] << '-' << remap[v] << endl;
                    } else {
// cerr << u << '-' << v << " illegal" << endl;
                    }
                }
                unordered_set<string> vis;
                vis.insert(zz);
                queue<string> q;
                q.push(zz);
                while (q.size()) {
                    string next = q.front();
                    q.pop();
                    for (auto [st, nd] : ss) {
                        if (!((next[st] - '0') ^ (next[nd] - '0'))) {
                            next[st] = ('0' + '1') - next[st]; 
                            next[nd] = ('0' + '1') - next[nd]; 
                            if (vis.find(next) == vis.end()) {
                                q.push(next);
                                vis.insert(next);
                            } else {
                            }
                            next[st] = ('0' + '1') - next[st]; 
                            next[nd] = ('0' + '1') - next[nd]; 
                        } else {
                        }
                    }
                }
                res *= (int)(size(vis));
                res %= modul;
// cerr << res << endl;
            }
            members[ix] = {};
        }
    }
    cout << res << endl;
}

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

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}