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

using namespace std;

const int N = 200'000 + 7;
const int M = 400'000 + 7;

const int mod = 1e9 + 7;

int fac[N], ifac[N], pot2[N];

int mul(int a, int b) {
	return int(1LL * a * b % mod);
}

int pot(int a, int b) {
	int r = 1;
	for (; b; b >>= 1, a = mul(a, a))
		if (b & 1)
			r = mul(r, a);
	return r;
}

int C(int n, int k) {
	if (k < 0 || k > n)
		return 0;
	return mul(fac[n], mul(ifac[k], ifac[n - k]));
}

int n, m, c[N];
vector<int> adj[N];
int color[N];
int vis[N];

vector<int> bucket[2];

bool dfs(int u, int col) {

	if (vis[u])
		return color[u] != col;

	bucket[col].push_back(u);

	color[u] = col;
	vis[u] = 1;

	bool odd_cycle = false;
	for (int v : adj[u]) {
		odd_cycle |= dfs(v, col ^ 1);
	}

	return odd_cycle;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n >> m;

	pot2[0] = 1;
	for (int i = 1; i <= n; i++)
		pot2[i] = mul(pot2[i - 1], 2);

	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = mul(fac[i - 1], i);

	ifac[n] = pot(fac[n], mod - 2);
	for (int i = n - 1; i >= 0; i--)
		ifac[i] = mul(ifac[i + 1], i + 1);
	
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	int ans = 1;
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			bucket[0].clear();
			bucket[1].clear();

			bool odd_cycle = dfs(i, 0);
			int sz = (int) (bucket[0].size() + bucket[1].size());

			if (odd_cycle) {
				ans = mul(ans, pot2[sz - 1]);
			}
			else {
				int ile = 0;
				for (int u : bucket[0])
					ile += (color[u] == c[u]);

				for (int u : bucket[1])
					ile += (color[u] == c[u]);

			// 	cerr << "> " << sz << ' ' << ile << " => " << sz << ' ' << ile << '\n';
				ans = mul(ans, C(sz, ile));
			}
		}
	}

	cout << ans << '\n';


	
	return 0;
}