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
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
		char c = getchar_unlocked(); a = 0;
		while(c<'0' || '9'<c) c = getchar_unlocked();
		while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = 1e09+7;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, int b){
		int ret = 1;
		while(b){
				if(b & 1) ret = mul(ret, a);
				b >>= 1, a = mul(a, a);
		} return ret;
}
int inv(int a){ return fpow(a, mod-2); }
int coeff(int n, int k, vector<int> &fac, vector<int> &invfac){
		if(n < k) return 0;
		return mul(fac[n], mul(invfac[n-k], invfac[k]));
}
void calcfac(int n, vector<int> &fac, vector<int> &invfac){
		fac[0] = 1, invfac[0] = 1;
		for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
		invfac[n] = inv(fac[n]);
		for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
}
void answer(){
		int n, m; scanf("%d%d", &n, &m);
		vv<vv<int>> g(n+1);
		vv<int> t(n+1, 0);
		for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
		for(int i = 0; i < m; ++i){
				int a, b; scanf("%d%d", &a, &b);
				g[a].emplace_back(b), g[b].emplace_back(a);
		}
		vv<int> col(n+1, -1), fac(n+1), invfac(n+1);
		calcfac(n, fac, invfac);
		int result = 1;
		for(int st = 1; st <= n; ++st) if(col[st] == -1){
				queue<int> q; q.emplace(st), col[st] = 0;
				vv<int> sz(2, 0), w(2, 0);
				bool bipartite = 1;
				int res = 0;
				while(!q.empty()){
						int x = q.front(); q.pop();
						++sz[col[x]];
						if(!t[x]) ++w[col[x]];
						for(int u : g[x]) if(col[u] == -1) col[u] = col[x]^1, q.emplace(u);
										  else if(col[u] == col[x]) bipartite = 0;
				}
				if(bipartite){
						if(w[0] > w[1]) swap(w[0], w[1]), swap(sz[0], sz[1]);
						int delta = w[1]-w[0];
						for(int i = 0; i <= sz[0] && i+delta <= sz[1]; ++i) res = add(res, mul(coeff(sz[0], i, fac, invfac), coeff(sz[1], i+delta, fac, invfac)));
				}
				else{
						w[0] += w[1], sz[0] += sz[1];
						for(int i = w[0]&1; i <= sz[0]; i += 2) res = add(res, coeff(sz[0], i, fac, invfac));
				}
				result = mul(result, res);
		}
		printf("%d\n", result);
}
signed main(){
		int T = 1;
		//~ scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
		for(++T; --T; ) answer();
		return 0;
}