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
125
126
127
128
129
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,_##i##__end=int(n);i<_##i##__end;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define rep1(i,n) for(int i=1,_##i##__end=int(n);i<=_##i##__end;++i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using namespace std;
const ll mod2=1000000007;
unsigned time_related_rand()
{
	return unsigned(std::chrono::steady_clock::now().time_since_epoch().count());
}
int n,m,u,v;
int c[200005];
ll answer=1;
struct dsu{
	int p[400005],s[400005];
	void init(int N)
	{
		rep1(i,N)
		{
			p[i]=i;s[i]=1;
		}
	}
	int getp(int x)
	{
		return (p[x]==x)?x:(p[x]=getp(p[x]));
	}
	bool same(int x,int y)
	{
		return getp(x)==getp(y);
	}
	void merge(int x,int y)
	{
		x=getp(x);y=getp(y);if(x==y)return;if(s[x]<s[y])swap(x,y);
		p[y]=x;s[x]+=s[y];
	}
	int size(int x)
	{
		return s[getp(x)];
	}
};
dsu P,Q;
int c0[200005],c1[200005],dif[200005];bool fl[200005];
ll fac[200005],ivf[200005];
ll qkpw(ll x,ll y)
{
	ll r=1;while(y)
	{
		if(y&1)r=r*x%mod2;x=x*x%mod2;y>>=1;
	}
	return r;
}
void init()
{
	fac[0]=1;rep1(i,n)fac[i]=fac[i-1]*i%mod2;
	ivf[n]=qkpw(fac[n],mod2-2);per(i,n)ivf[i]=ivf[i+1]*(i+1)%mod2;
}
ll C(int x,int y)
{
	if(y<0||y>x)return 0;return ivf[y]*ivf[x-y]%mod2*fac[x]%mod2;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>m;rep1(i,n)cin>>c[i];P.init(n);Q.init(2*n);
	init();
	rep1(i,m)
	{
		cin>>u>>v;P.merge(u,v);Q.merge(u,v+n);Q.merge(u+n,v);
	}
	rep1(i,n) if(P.getp(i)==i)
	{
	//	cout<<"Root : "<<i<<endl;
		if(Q.same(i,i+n))
		{
	//		cout<<"Cycled : "<<P.size(i)<<endl;
			answer=answer*qkpw(2,P.size(i)-1)%mod2;
		}
		else
		{
		//	cout<<"Binary : "<<endl;
			fl[i]=true;
		}
	}
	rep1(i,n)
	{
		if(Q.same(i,P.getp(i)))
		{
			++c0[P.getp(i)];dif[P.getp(i)]+=c[i];
		}
		else
		{
			++c1[P.getp(i)];dif[P.getp(i)]-=c[i];
		}
	}
	rep1(i,n) if(fl[i])
	{
	//	cout<<c0[i]<<' '<<c1[i]<<' '<<dif[i]<<endl;
		answer=answer*C(c0[i]+c1[i],c0[i]-dif[i])%mod2;
	}
	cout<<answer<<endl;
	return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/