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

using namespace std;

const int N = 2e5 + 5, Mod = 1e9 + 7;

inline int power(int x, int y){
	int ret = 1;
	while(y){
		if(y & 1) ret = 1ll * ret * x % Mod;
		x = 1ll * x * x % Mod, y >>= 1;
	}
	return ret;
}

inline int inv(int x){
	return power(x, Mod - 2);
}

int fac[N] = {}, ifac[N] = {}, ans = 1;

inline int C(int n, int m){
	return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}

int n = 0, m = 0, d[N] = {}, c[N] = {}, k = 0, x = 0, y = 0, a = 0, b = 0;
vector<vector<int> > G(N);

inline void dfs(int u, int w){
	c[u] = w;
	if(w) a ++, x += d[u]; else b ++, y += d[u];
	for(int v : G[u]){
		if(c[v] == -1) dfs(v, w ^ 1);
		else if(c[u] == c[v]) k = 1;
	}
}

int main(){
	fac[0] = ifac[0] = 1;
	for(int i = 1 ; i < N ; i ++) fac[i] = 1ll * fac[i - 1] * i % Mod, ifac[i] = inv(fac[i]);
	scanf("%d %d", &n, &m);
	for(int i = 1 ; i <= n ; i ++) scanf("%d", &d[i]);
	for(int i = 1, u = 0, v = 0 ; i <= m ; i ++){
		scanf("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	memset(c, -1, sizeof(c));
	for(int u = 1 ; u <= n ; u ++) if(c[u] == -1){
		int ret = 0;
		k = x = y = a = b = 0;
		dfs(u, 0);
		if(k){
			a = a + b, x = (x + y) & 1;
			while(x <= a){
				ret = (ret + C(a, x)) % Mod;
				x += 2;
			}
		}
		else{
			int z = min(x, y);
			x -= z, y -= z;
			while(x <= a && y <= b){
				ret = (ret + 1ll * C(a, x) * C(b, y)) % Mod;
				x ++, y ++;
			}
		}
		ans = 1ll * ans * ret % Mod;
	}
	printf("%d\n", ans);
	return 0;
}