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

using namespace std;
typedef long long ll;
const int MAXN=2e5;
const ll MOD = 1e9+7;

map<string, bool> M;
vector<pair<int, int>> przelaczniki;
vector<int> adj[MAXN+5];
bool vis[MAXN+5];

vector<pair<int, int>> W;
void dfs1(int v, int p)
{
	vis[v]=1;
	for(int u : adj[v]){
		if(u!=p){
			W.push_back({v, u});
			if(!vis[u]) dfs1(u, v);
		}
	}
}

void dfs2(string s)
{
	M[s]=1;
	int m = W.size();
	for(int i=0;i<m;i++){
		int a = W[i].first;
		int b = W[i].second;
		a--; b--;
		if(s[a] == s[b]){
			string w = s;
			if(w[a]=='0'){
				w[a]='1';
				w[b]='1';
			}
			else{
				w[a]='0';
				w[b]='0';
			}
			if(!M[w]) dfs2(w);
		}
	}
}

void solve()
{
	int n, m;
	cin >> n >> m;
	string s;
	for(int i=0;i<n;i++){
		char a;
		cin >> a;
		s+=a;
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >> b;
		przelaczniki.push_back({a, b});
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	ll ans=1;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			W.clear();
			M.clear();
			dfs1(i, i);
			dfs2(s);
			ans = (ans * (ll)M.size()) % MOD;
		}
	}
	cout << ans;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	
	return 0;
}