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
#include <iostream>
#include <set>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 200002;
const int MAXM = 400002;
vector<bool> visited(MAXN);
vector<vector<int>> graph(MAXN);
vector<bool> initial_state(MAXN);

const int MOD = 1e9 + 7;

// Here base is assumed to be 2
int cal_pow(int x)
{
	long long res;
	if (x == 0)
		res = 1;
	else if (x == 1)
		res = 2;
	else
	{
		res = cal_pow(x / 2);
		if (x % 2 == 0)
			res = (res * res) % MOD;
		else
			res = (((res * res) % MOD) * 2) % MOD;
	}
	return res;
}

// BFS dla obliczania liczby wierzchołków i krawędzi w podgrafie
pair<vector<int>, int> bfs(int start)
{
	vector<int> verts = {start};
	visited[start] = true;
	stack<int> s;
	s.push(start);
	int vertices = 0;  // Liczba wierzchołków w podgrafie
	int edges = 0;     // Liczba krawędzi w podgrafie

	while (!s.empty())
	{
		int v = s.top();
		s.pop();
		vertices++;

		for (int u : graph[v])
		{
			if (!visited[u])
			{
				visited[u] = true;
				s.push(u);
				verts.push_back(u);
			}
			edges++;  // Zliczamy tylko krawędzie wychodzące z aktualnego wierzchołka, które nie zostały jeszcze odwiedzone
		}
	}

	return {verts, edges};
}

int main()
{
	int n, m;
	cin >> n >> m;

	initial_state.resize(n);
	graph.resize(n);
	visited.resize(n, false);
	for (int i = 0; i < n; ++i)
	{
		int state;
		cin >> state;
		initial_state[i] = state;
	}

	// Wczytaj informacje o przełącznikach i zapisz do grafu
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		graph[a - 1].push_back(b - 1);  // Przejście z a do b (indeksowane od 0)
		graph[b - 1].push_back(a - 1);  // Przejście z b do a (indeksowane od 0)
	}

	vector<pair<vector<int>, int>> subgraph_info;  // Przechowuje informacje o liczbie wierzchołków i krawędzi w każdym podgrafie

	for (int i = 0; i < n; ++i)
	{
		if (!visited[i])
		{
			auto [vertices, edges] = bfs(i);
			subgraph_info.push_back({vertices, edges / 2});  // Dzielimy przez 2, ponieważ każda krawędź została zliczona dwukrotnie
		}
	}

	long long posibilities = 1;
	int oneCnt = 0;
	int twoCnt = 0;
	for (int i = 0; i < subgraph_info.size(); ++i)
	{
		if (subgraph_info[i].first.size() == 1)
		{
			oneCnt++;
			continue;
		}
		if (subgraph_info[i].first.size() == 2)
		{
			twoCnt++;
			if (initial_state[subgraph_info[i].first[0]] == initial_state[subgraph_info[i].first[1]]) posibilities = (posibilities * 2) % MOD;
			continue;
		}
		// cout << "Podgraf " << i + 1 << ": " << subgraph_info[i].first.size() << " wierzcholkow, " << subgraph_info[i].second << " krawedzi" << endl;
		posibilities = (posibilities * cal_pow(subgraph_info[i].first.size() - 1)) % MOD;
	}

	// cout << "Pojedynczych wierzcholkow: " << oneCnt << " mozliwosci: " << posibilities << endl;
	// cout << "Podwojnych wierzcholkow: " << twoCnt << endl;

	cout << posibilities << endl;

	return 0;
}