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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1e9+7;
ll silnie[200001];
ll dwapot[200001];
ll fastpot(ll a, ll b){
	ll w = 1;
	while (b){
		if (b%2) w = (w*a)%mod;
		a = (a*a)%mod;
		b /= 2;
	}	
	return w%mod;
}
ll inv(ll x){
	return fastpot(x,mod-2);
}
ll dwumian(ll n, ll k){
	return ((silnie[n]*inv(silnie[n-k]))%mod*inv(silnie[k]))%mod;
}
bool vis[200001];
bool kolor[200001];
vector<ll> spojna;
vector<ll> sas[200001];
void DFS(ll v){
	vis[v] = 1;
	spojna.push_back(v);
	for (ll u : sas[v]){
		if (vis[u]) continue;
		kolor[u] = kolor[v]^1;
		DFS(u);
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll i;
	ll n,m;
	cin>>n>>m;
	bool tab[n+1];
	silnie[0] = 1;
	dwapot[0] = 1;
	for (i = 1; i <= n; i++){
		cin>>tab[i];
		silnie[i] = (silnie[i-1]*i)%mod;
		dwapot[i] = (dwapot[i-1]*2)%mod;
	}
	while (m--){
		int a,b;
		cin>>a>>b;
		sas[a].push_back(b);
		sas[b].push_back(a);
	}	
	ll wy = 1;
	for (i = 1; i <= n; i++){
		if (vis[i]) continue;
		spojna.clear();
		DFS(i);
		ll k = 0;
		bool czykolor = 1;
		for (ll v : spojna){
			if (kolor[v] != tab[v]) k++;
			for (ll u : sas[v]){
				if (kolor[v] == kolor[u]) czykolor = 0;
			}
		}
		ll m = spojna.size();
		if (!czykolor){
			wy = (wy*dwapot[m-1])%mod;
		}else{
			wy = (wy*dwumian(m,k))%mod;
		}
	}
	cout<<wy%mod<<"\n";
	return 0;
}