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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;

set<vector<int>> stany;
void solve(vector<int> &v, const vector<pair<int, int>> &w)
{
	for (auto [x, y] : w)
	{
		if (v[x] == v[y])
		{
			v[x] = v[y] = !v[x];
			if (stany.find(v) == stany.end())
			{
				stany.insert(v);
				solve(v, w);
			}
			v[x] = v[y] = !v[x];
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m;
	cin >> n >> m;
	vector<int> v(n);
	for (auto &e : v)
		cin >> e;
	vector<pair<int, int>> w(m);
	for (auto &e : w)
	{
		cin >> e.first >> e.second;
		e.first--;
		e.second--;
	}
	solve(v, w);
	cout << stany.size()%mod << "\n";
}