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
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, b, e) for(int i = (b); i < (e); i++)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
					((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

const int mod = 1e9 + 7;

vector<vi> G;
vi col, vis, dpth;
vi fact, ifact;

int pov(int base, int exp) {
	int res = 1;
	for(; exp > 0; exp >>= 1) {
		if(exp & 1) res = 1ll * res * base % mod;
		base = 1ll * base * base % mod;
	}
	return res;
}

int binom(int n, int k) {
	return 1ll * fact[n] * ifact[n - k] % mod * ifact[k] % mod;
}

void dfs(int v, vi &par, vi &par_zap, bool &ncyc, int d) {
	vis[v] = 1;
	dpth[v] = d;
	if(col[v]) par_zap[d]++;
	par[d]++;
	for(auto &x: G[v]) {
		if(!vis[x]) dfs(x, par, par_zap, ncyc, d ^ 1);
		if(dpth[x] == dpth[v]) ncyc = 1;
	}
}

int licz(int v) {
	vi par(2), par_zap(2);
	bool ncyc = 0;
	dfs(v, par, par_zap, ncyc, 0);
	int n = par[0] + par[1];
	if(ncyc) return pov(2, n - 1);
	if(par_zap[0] < par_zap[1]) swap(par[0], par[1]), swap(par_zap[0], par_zap[1]);
	int mini_zap = par_zap[0] - par_zap[1];
	int res = 0;
	for(int zap = mini_zap, dod = 0; zap <= par[0] && dod <= par[1]; zap++, dod++) {
		res = (res + 1ll * binom(par[0], zap) * binom(par[1], dod)) % mod;
	}
	return res;
}

void solve() {
	int n, m;
	cin >> n >> m;
	fact.resize(n + 1, 1), ifact.resize(n + 1, 1);
	FOR(i, 0, n) {
		fact[i + 1] = ll(i + 1) * fact[i] % mod;
		ifact[i + 1] = pov(fact[i + 1], mod - 2);
	}
	G.resize(n), col.resize(n), vis.resize(n), dpth.resize(n);
	for(auto &x: col) cin >> x;
	FOR(i, 0, m) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		G[a].pb(b), G[b].pb(a);
	}
	int ans = 1;
	FOR(i, 0, n) if(!vis[i]) ans = 1ll * ans * licz(i) % mod;
	cout << ans << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin >> tt;
	FOR(te, 0, tt) solve();
	return 0;
}