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
#include<bits/stdc++.h>
using namespace std;

vector<int> graf[200009];
bool zar[200009];
long long N, N1, N2, P1, P2, N1P1, N2P2, bip;
long long powers[200009], col[200009];
const long long M = 1e9 + 7;

void DFS(int u, int c)
{
	int a;
	N++;
	col[u] = c;
	if(c == 1)
	{
		N1++;
		if(zar[u]) P1++;
	}
	else
	{
		N2++;
		if(zar[u]) P2++;
	}
	for(int i=0; i<graf[u].size(); i++)
	{
		a = graf[u][i];
		if(col[a] == c) bip = 1;
		else if(col[a] == 0) DFS(a, 3-c);
	}
	return;
}

long long fast_pow(long long a, long long p)
{
	if(p == 0) return 1;
	if(p == 1) return a;
	long long b = fast_pow(a, p/2);
	if(p % 2 == 1) b = (((b * b) % M) * a) % M;
	else b = (b * b) % M;
	return b;
}

long long choose(long long n, long long k)
{
	long long wyn = 1, d = 1;
	for(long long i=k+1; i<=n; i++) wyn = (wyn * i) % M;
	for(long long i=1; i<=n-k; i++) d = (d * i) % M;
	wyn = (wyn * fast_pow(d, M-2)) % M;
	return wyn;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	long long n, m, a, b, c, wyn = 1;
	cin>>n>>m;
	powers[1] = 1;
	for(int i=2; i<=n; i++) powers[i] = (2 * powers[i-1]) % M;
	for(int i=1; i<=n; i++) cin>>zar[i];
	for(int i=1; i<=m; i++)
	{
		cin>>a>>b;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	for(int i=1; i<=n; i++)
	{
		if(col[i] == 0)
		{
			N = N1 = N2 = P1 = P2 = bip = 0;
			DFS(i, 1);
			if(bip == 0)						// spójna dwudzielna
			{
				a = min(P1, P2);
				P1 -= a;
				P2 -= a;
				b = min(N1 - P1, N2 - P2);
				N1P1 = choose(N1, P1);
				N2P2 = choose(N2, P2);
				c = (N1P1 * N2P2) % M;
				for(long long k=0; k<b; k++)
				{
					N1P1 = (N1P1 * (N1 - P1 - k)) % M;
					N1P1 = (N1P1 * fast_pow(P1 + k + 1, M-2)) % M;
					N2P2 = (N2P2 * (N2 - P2 - k)) % M;
					N2P2 = (N2P2 * fast_pow(P2 + k + 1, M-2)) % M;
 					c = (((N1P1 * N2P2) % M) + c) % M;
				}
				wyn = (wyn * c) % M;
			}
			else wyn = (wyn * powers[N]) % M;	// spójna niedwudzielna
		}
	}
	cout<<wyn;
    return 0;
}