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
130
131
132
133
134
135
136
137
138
139
140
141
142
//
// Created by piotr on 16.03.2024.
//
#include <algorithm>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <list>
#include <iostream>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using Edge = std::pair<int,int>;
using EdgeVector = std::vector<Edge>;

const signed char NONE = 0;
const signed char BLACK = -1; // a bit racist
const signed char WHITE = +1;

std::vector<EdgeVector::iterator> begins;
std::vector<EdgeVector::iterator> ends;

const long long MODULO = 1000000007;

std::tuple<long long, long long, long long> extended_gcd(long long a, long long b) {
	if (b == 0) {
		return {1, 0, a};
	}
	auto [x1, y1, gcd] = extended_gcd(b, a % b);
	return {y1, x1 - (a / b) * y1, gcd};
}

long long mod_inverse(long long a, long long m = MODULO) {
	long long x, y, gcd;
	std::tie(x, y, gcd) = extended_gcd(a, m);
	if (gcd != 1) {
		return -1;
	}
	return (x % m + m) % m;
}

long long mod_multiply(long long a, long long b, long long m = MODULO) {
	return (a * b) % m;
}

bool is_special(int root, std::vector<signed char>& states, std::list<int>& nodes) {
	std::queue<int> bfs;
	states[root] = WHITE;
	bfs.push(root);

	bool is_special_graph = 0;
	while (!bfs.empty()) {
		const int here = bfs.front();
		bfs.pop();
		nodes.push_back(here);

		for (EdgeVector::iterator it=begins[here]; it!=ends[here]; ++it) {
			const int there = it->second;
			if (states[there]) {
				if (states[there] == states[here]) {
					is_special_graph = true;
				}
			} else {
				states[there] = -states[here];
				bfs.push(there);
			}
		}
	}
	return is_special_graph;
}

int main() {
	int N, M;
	assert(scanf("%d%d", &N, &M) == 2);

	std::vector<int> configuration(N);
	for (int n=0; n<N; ++n) {
		assert(scanf("%d", &configuration[n]) == 1);
	}

	EdgeVector edges;
	edges.reserve(M);
	for (int m=0; m<M; ++m) {
		int a, b;
		assert(scanf("%d%d", &a, &b) == 2);
		edges.push_back({a-1, b-1});
		edges.push_back({b-1, a-1});
	}

	std::sort(edges.begin(), edges.end());
	std::vector<int> edge_counts(N, 0);
	for (const Edge& edge : edges) {
		edge_counts[edge.first]++;
	}

	begins.resize(N);
	ends.resize(N);
	EdgeVector::iterator it = edges.begin();
	for (int i=0; i<N; ++i) {
		begins[i] = it;
		it += edge_counts[i];
		ends[i] = it;
	}

	std::vector<long long> factorials(N+1);
	std::vector<long long> powers_of_two(N+1);
	factorials[0] = 1;
	powers_of_two[0] = 1;
	for (int i=1; i<=N; ++i) {
		factorials[i] = mod_multiply(factorials[i-1], i);
		powers_of_two[i] = mod_multiply(powers_of_two[i-1], 2);
	}

	long long result = 1;
	std::vector<signed char> states(N, NONE);
	for (int root=0; root<N; ++root) {
		if (states[root]) {
			continue;
		}
		std::list<int> nodes;
		if (is_special(root, states, nodes)) {
			int count = nodes.size();
			result = mod_multiply(result, powers_of_two[count - 1]);
		} else {
			int count = nodes.size();

			int checksum = 0;
			for (int node : nodes) {
				checksum += states[node] * (2 * configuration[node] - 1);
			}
			int bottom = (count - abs(checksum)) / 2;
			result = mod_multiply(result,
				mod_multiply(factorials[count], mod_inverse(
					mod_multiply(factorials[count - bottom], factorials[bottom])
				))
			);
		}
	}
	printf("%lld\n", result);
}