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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1000000007ll;
#define pb push_back

int INT() {
	int in; scanf("%d", &in);
	return in;
}

ll power(ll a, int b) {
	if(!b) return 1ll;
	if(b&1) return (a*power(a, b-1))%mod;
	ll ret=power(a, b>>1);
	return (ret*ret)%mod;
}

vector <ll> fac, fac1;

void prep(int n) {
	fac.resize(n+1), fac1.resize(n+1);
	fac[0]=1;
	for(int i=1; i<=n; ++i) fac[i]=(fac[i-1]*ll(i))%mod;
	fac1[n]=power(fac[n], int(mod)-2);
	for(int i=n-1; i>=0; --i) fac1[i]=(fac1[i+1]*ll(i+1))%mod;
}

ll binom(int n, int k) {
	return (((fac[n]*fac1[k])%mod)*fac1[n-k])%mod;
}

vector <vector <int> > g;
vector <int> state;

bool bipartite;
int a, b, z, za, zb;
vector <int> col;

void dfs(int x, int c) {
	col[x]=c;
	if(c) ++b;
	else ++a;
	if(state[x]) {
		++z;
		if(c) ++zb;
		else ++za;
	}
	int cu=1;
	if(c) cu=0;
	for(int &u : g[x]) {
		if(col[u]==-1) dfs(u, cu);
		else if(col[u]==c) bipartite=0;
	}
}

int main() {
	int n=INT(), m=INT();
	prep(n);
	g.resize(n+1), state.resize(n+1), col.resize(n+1, -1);
	for(int x=1; x<=n; ++x) state[x]=INT();
	for(int i=0; i<m; ++i) {
		int A=INT(), B=INT();
		g[A].pb(B), g[B].pb(A);
	}
	
	ll ans=1ll;
	for(int x=1; x<=n; ++x) if(col[x]==-1) {
		bipartite=1;
		a=0, b=0, z=0, za=0, zb=0;
		dfs(x, 0);

		//printf("x:%d a:%d b:%d z:%d za:%d zb:%d bipartite:%d\n", x, a, b, z, za, zb, bipartite?1:0);

		ll sum=0ll;
		if(!bipartite) {
			for(int k=z&1; k<=a+b; k+=2) sum+=binom(a+b, k);
			sum%=mod;
		}
		else {
			if(za<zb) swap(a, b), swap(za, zb);
			za-=zb, zb=0;
			for(; zb<=b && za<=a; ++za, ++zb) sum+=(binom(a, za)*binom(b, zb))%mod;
			sum%=mod;
		}
		//printf("%lld\n", sum);
		ans=(ans*sum)%mod;
	}
	printf("%lld\n", ans);
	exit(0);
}