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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 200'009;
const int MOD = 1e9+7;

vector<int> G[MAXN];
int col[MAXN];
int ans = 1;
int type[MAXN];
int fact[MAXN];
int fact_inv[MAXN];
int pow2[MAXN];

bool is2;
vector<int> v;
void dfs(int x, int t) {
	type[x] = t;
	v.pb(x);
	for(int y:G[x]) {
		if(type[y]==0) {
			dfs(y, 3-t);
		} else if(type[y]==t) {
			is2 = false;
		}
	}
}

int C(int a, int b) {
	return fact[a]*fact_inv[b]%MOD*fact_inv[a-b]%MOD;
}

int f(int a, int b) {
	int c = 1;
	while(b) {
		if(b%2)
			c = c*a%MOD;
		a = a*a%MOD;
		b/=2;
	}
	return c;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	pow2[0] = 1;
	for(int i=1;i<MAXN;i++) pow2[i] = pow2[i-1]*2%MOD;
	fact[0] = 1;
	for(int i=1;i<MAXN;i++) fact[i] = fact[i-1]*i%MOD;
	fact_inv[MAXN-1] = f(fact[MAXN-1], MOD-2);
	for(int i=MAXN-2;i>=0;i--) fact_inv[i] = fact_inv[i+1]*(i+1)%MOD;
	
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		cin >> col[i];
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i=1;i<=n;i++) {
		if(type[i]) continue;
		is2 = true;
		v.clear();
		dfs(i, 1);
		if(is2) {
			int res = 0;
			int sz1 = 0, sz2 = 0;
			int cnt1 = 0, cnt2 = 0;
			bool yes = false;
			for(int x:v) {
				for(int y:G[x]) {
					if(col[x]==col[y]) {
						yes = true;
					}
				}
				if(type[x]==1) {
					sz1++;
					if(col[x]) cnt1++;
				} else {
					sz2++;
					if(col[x]) cnt2++;
				}
			}
			if(!yes) continue;
			int Min = min(cnt1, cnt2);
			cnt1-=Min, cnt2-=Min;
			while(cnt1<=sz1&&cnt2<=sz2) {
				res += C(sz1, cnt1)*C(sz2, cnt2);
				res %= MOD;
				cnt1++, cnt2++;
			}
			ans = ans*res%MOD;
		} else {
			ans = ans*pow2[sz(v)-1]%MOD;
		}
	}
	cout << ans << "\n";
}