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
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define gc getchar_unlocked
using namespace std;
typedef long long ll;
constexpr ll mod = 1000000007ll;

void wczytaj(int &a){
	int c = gc();
	while(c < '0' || c > '9') c = gc();
	for(a = 0; c >= '0' && c <= '9'; c = gc()) a = 10*a+c-'0';
}

ll pot(ll a, ll b = mod-2ll){
	ll ret = 1ll;
	for(; b; b>>=1, a=(a*a)%mod) if(b&1ll) ret = (ret*a)%mod;
	return ret;
}

void solve(){
	int n, m;
	wczytaj(n), wczytaj(m);
	vector<int> wej(n+1);
	FOR(i, 1, n) wczytaj(wej[i]);
	vector<vector<int>> g(n+1);
	while(m--){
		int a, b;
		wczytaj(a), wczytaj(b);
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	
	vector<ll> sil(n+1, 1ll), odwsil(n+1, 1ll);
	FOR(i, 1, n) sil[i] = (sil[i-1]*ll(i))%mod;
	odwsil[n] = pot(sil[n]);
	for(int i = n; --i;) odwsil[i] = (odwsil[i+1]*ll(i+1))%mod;
	auto dwumian = [&](int nn, int kk){
		return (sil[nn] * ((odwsil[kk]*odwsil[nn-kk])%mod))%mod;
	};
	
	ll wyn = 1ll;
	vector<bool> odw(n+1, 0), kol(n+1, 0);
	FOR(start, 1, n) if(!odw[start]){
		int rozmiar = 0, suma = 0, kulki = 0;
		bool operacja = 0, dwudzielnosc = 1;
		function<void(int)> dfs = [&](int w){
			odw[w] = 1, ++rozmiar, suma += kol[w], kulki += kol[w]^wej[w];
			for(int i : g[w]){
				if(!odw[i]) kol[i] = !kol[w], dfs(i);
				if(wej[w] == wej[i]) operacja = 1;
				if(kol[w] == kol[i]) dwudzielnosc = 0;
			}
		};
		dfs(start);
		if(!operacja) continue;
		ll tmp = 0ll;
		if(dwudzielnosc) tmp = dwumian(rozmiar, kulki);
		else for(tmp = 1ll; --rozmiar;) tmp = (tmp<<1)%mod;
		wyn = (wyn*tmp)%mod;
	}
	printf("%lld", wyn);
}

int main(){
	solve();
	return 0;
}