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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int Q = 1'000'000'007;

int mn(long long a, int b) {
	return (a * b) % Q;
}

void dod(int& x, int y) {
	x += y;
	if (x >= Q) x -= Q;
}

int pot(int x, int n) {
	int ret = 1;
	for(; n; n /= 2) {
		if (n % 2) ret = mn(ret, x);
		x = mn(x, x);
	}
	return ret;
}

const int M = 201'013;
int odw[M];

vector<int> nk(int n) {
	vector<int> r(n+1);
	r[0] = 1;
	for (int i = 1; i <= n; i++) {
		r[i] = mn(r[i-1], mn(n-i+1, odw[i]));
	}
	return r;
}

struct wyn {
	int typ = 0;
	int l = 0, p = 0, r = 0;
};

int c[M], zap[M];
vector<int> v[M];

void dfs(int x, int kol, wyn& ret) {
	c[x] = kol;
	if (kol == 2) ret.p++;
	else ret.l++;
	if (zap[x]) {
		if (kol == 2) ret.r--;
		else ret.r++;
	}
	for (int i : v[x]) {
		if(!c[i]) dfs(i, 3-kol, ret);
		else if (c[i] == kol) ret.typ = 1;
	}
}

int main() {
	int n, m;
	scanf("%d %d", &n,&m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &zap[i]);
		odw[i+1] = pot(i+1, Q-2);
	}
	int a,b;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &a, &b);
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int ret = 1;
	for (int i = 0; i < n; i++) if(!c[i]) {
		wyn x;
	  dfs(i, 1, x);
		int w = 0;
		//printf("typ=%d l=%d, p=%d, roz=%d\n",x.typ,x.l,x.p,x.r);
		if (x.typ) w = pot(2, x.l+x.p-1);
		else {
			vector<int> l = nk(x.l);
			vector<int> p = nk(x.p);
			for (int i = 0; i <= x.l; i++) 
				if (i-x.r >= 0 && i-x.r <= x.p)
					dod(w, mn(l[i], p[i-x.r]));
		}
		//printf("%d\n", w);
		ret = mn(ret, w);
	}
  printf("%d\n", ret);
	return 0;
}