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
113
114
115
116
117
118
119
120
121
122
123
124
//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
ll fact[N],inv[N],inv_fac[N];
ll n,m,a[N],col[N];
vector<ll> vt[N],pth;
bool ok1,ok2,vis[N];
void dfs(ll x,ll c)
{
	col[x]=c;
	pth.push_back(x);
	vis[x]=true;
	ll i;
	for(i=0;i<vt[x].size();i++)
	{
		if(a[x]==a[vt[x][i]])
		{
			ok1=true;
		}
		if(!vis[vt[x][i]])
		{
			dfs(vt[x][i],c^1);
		}
		else if(col[vt[x][i]]==c)
		{
			ok2=false;
		}
	}
	return;
}
ll C(ll x,ll y){return (x<y||x<0||y<0)?0:(fact[x]*((inv_fac[y]*inv_fac[x-y])%mod))%mod;}
int main(){
	ll i,j,x,y;
	fact[0]=inv_fac[0]=inv[1]=inv_fac[1]=fact[1]=1;
	for(i=2;i<N;i++)
	{
		fact[i]=(fact[i-1]*i)%mod;
		inv[i]=(inv[mod%i]*(mod-mod/i))%mod;
		inv_fac[i]=(inv_fac[i-1]*inv[i])%mod;
	}
	scanf("%lld%lld",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(i=0;i<m;i++)
	{
		scanf("%lld%lld",&x,&y);
		x--,y--;
		vt[x].push_back(y);
		vt[y].push_back(x);
	}
	ll ans=1;
	for(i=0;i<n;i++)
	{
		if(vis[i])
		{
			continue;
		}
		ok1=false,ok2=true;
		pth.clear();
		dfs(i,0);
		if(!ok1)
		{
			continue;
		}
		if(!ok2)
		{
			ll tot=pth.size(),cnt=0;
			for(j=0;j<pth.size();j++)
			{
				cnt+=a[pth[j]];
			}
			ll sum=0;
			for(j=cnt&1;j<=tot;j+=2)
			{
				sum=(sum+C(tot,j))%mod;
			}
			ans=(ans*sum)%mod;
		}
		else
		{
			ll tot0=0,tot1=0,cnt0=0,cnt1=0;
			for(j=0;j<pth.size();j++)
			{
				if(col[pth[j]])
				{
					tot1++;
					cnt1+=a[pth[j]];
				}
				else
				{
					tot0++;
					cnt0+=a[pth[j]];
				}
			}
			ll sum=0;
			for(j=0;j<=tot0;j++)
			{
				x=cnt1-(cnt0-j);
				if(x>=0&&x<=tot1)
				{
					sum=(sum+C(tot0,j)*C(tot1,x))%mod;
				}
			}
			ans=(ans*sum)%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}