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
// 2024 HOPE IN VALUABLE
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const int mod=1000000007;
inline int qpow(int x,int y){
	int r=1; while(y){
		if(y&1) r=1ll*r*x%mod;
		x=1ll*x*x%mod; y>>=1;
	}	return r;
}
inline void add(int &x,int y){ if((x+=y)>=mod) x-=mod; }
int n,m,ans=1,a[N],col[N],fl[N],qwq[N][2][2],o[N],ff[N],sz[N],fac[N],ifac[N];
inline int C(int n,int m){
	if(n<m||m<0) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int find(int x){ return ff[x]==x?x:ff[x]=find(ff[x]); }
struct Edge{ int to,nxt; }e[N<<2]; int head[N],etot;
inline void ade(int u,int v){ e[++etot]={v,head[u]}; head[u]=etot; }
inline void dfs(int u){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(col[u]==col[v]) fl[find(u)]=1;
		else if(col[v]==-1) col[v]=col[u]^1,dfs(v);
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=qpow(fac[n],mod-2); for(int i=n-1;~i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++) cin>>a[i],ff[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w=0; cin>>u>>v;
		ff[find(u)]=find(v);
		ade(u,v); ade(v,u);
		if(a[u]==a[v]) o[u]=o[v]=1;
	}
	for(int i=1;i<=n;i++) col[i]=-1; for(int i=1;i<=n;i++) if(col[i]==-1) col[i]=0,dfs(i);
	for(int i=1;i<=n;i++) sz[find(i)]++,o[find(i)]|=o[i],qwq[find(i)][col[i]][a[i]]++;
	for(int i=1;i<=n;i++) if(ff[i]==i){
		if(!o[i]) continue;
		if(fl[i]){
			sz[i]--;
			while(sz[i]--) ans=ans*2%mod;
		}
		else{
			int tmp=0;
			for(int j=0;j<=qwq[i][0][0]+qwq[i][0][1];j++){
				int delta=j-qwq[i][0][0];
				int x=qwq[i][1][0]+delta;
				if(x<0) continue;
				add(tmp,1ll*C(qwq[i][0][0]+qwq[i][0][1],j)*C(qwq[i][1][0]+qwq[i][1][1],x)%mod);
			}
			ans=1ll*ans*tmp%mod;
		}
	}	cout<<ans<<'\n';
	return 0;
}