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
#include <cstdio>
#include <cstdint>
#include <vector>
#include <queue>

using namespace std;

const int64_t MOD = 1000000007;

typedef struct {
	vector<int> adj;
	bool on;
	bool visited;
	bool right;
} node_t;

vector<int64_t> P2s;
vector<int64_t> F;

int64_t ext_euclid(int64_t a, int64_t b, int64_t &x, int64_t &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64_t x1, y1;
	int64_t gcd = ext_euclid(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

int64_t inverse(int64_t a) {
    int64_t x, y;
    ext_euclid(a, MOD, x, y);
    return x;
}

int64_t BC(int64_t n, int64_t k) {
    int64_t ret = (((F[n] * inverse(F[k])) % MOD) * inverse(F[n - k])) % MOD;
	return ret >= 0 ? ret : ret + MOD;
}


int main () {

	P2s.reserve(200032);
	int64_t p2 = 1;
	for (int i = 0; i < 200016; ++i) {
		P2s.push_back(p2);
		p2 = (p2 << 1) % MOD;
	}

	F.reserve(200032);
	int64_t f = 1;
	for (int i = 0; i < 200016; ++i) {
		F.push_back(f);
		f = (f * (i + 1)) % MOD;
	}

	int n, m;
	scanf("%d %d", &n, &m);
	node_t node;
	node.on = false;
	node.visited = false;
	node.right = false;
	vector<node_t> graph(n, node);
	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		graph[i].on = (x == 1);
	}
	for (int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		graph[x].adj.push_back(y);
		graph[y].adj.push_back(x);
	}

	int64_t res = 1;
	queue<pair<int, bool> > q;
	for (int i = 0; i < n; ++i) {
		if (graph[i].visited) {
			continue;
		}
		bool bipartite = true;
		int size = 0;
		int k = 0;
		q.push(make_pair(i, false));
		while (!q.empty()) {
			pair<int, bool> item = q.front();
			int node_i = item.first;
			bool is_right = item.second;
			q.pop();
			if (graph[node_i].visited) {
				if (graph[node_i].right != is_right) {
					bipartite = false;
				}
				continue;
			}
			graph[node_i].visited = true;
			graph[node_i].right = is_right;
			++size;
			if (is_right) {
				if (graph[node_i].on) {
					++k;
				}
			}
			else {
				if (!graph[node_i].on) {
					++k;
				}
			}
			for (vector<int>::iterator it = graph[node_i].adj.begin(); it != graph[node_i].adj.end(); it++) {
				q.push(make_pair(*it, !is_right));
			}
		}
		if (bipartite) {
			res = (res * BC((int64_t)size, (int64_t)k)) % MOD;
		}
		else {
			res = (res * P2s[size - 1]) % MOD;
		}
	}
	printf("%lld\n", res);
	return 0;
}