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 <cstdio>
#include <queue>
#include <set>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define SIZE(c) ((int)(c).size())
#define MP make_pair
#define FT first
#define SD second
#define INT(x) int x; scanf("%d", &x)

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

const int N = 27;
const int mod = 1000000007;
int c[200000];
VVI g;
set<PII> e;
int x[1 << N];
bool seen[200000];
VI p;
int pp[200000];

void go(int v, int vv = -1) {
	if (vv >= 0) e.insert(MP(min(v, vv), max(v, vv)));
	if (seen[v]) return;
	seen[v] = 1;
	p.PB(v);
	FORE(it,g[v]) go(*it, v);
}

int main() {
	INT(n);
	INT(m);
	REP(i,n) scanf("%d", &c[i]);
	g.resize(n);
	REP(j,m) {
		INT(a);
		INT(b);
		--a;
		--b;
		g[a].PB(b);
		g[b].PB(a);
	}
	int r = 1;
	REP(i,n) {
		if (seen[i]) continue;
		int rr = 1;
		e.clear();
		p.clear();
		go(i);
		int sp = SIZE(p);
		REP(ppp,sp) pp[p[ppp]] = ppp;
		int cc = 0;
		REP(ppp,sp) if (c[p[ppp]]) cc |= 1 << ppp;
		x[cc] = i + 1;
		queue<int> q;
		q.push(cc);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			FORE(it,e) {
				if (!!(v & (1 << pp[it->FT])) == !!(v & (1 << pp[it->SD]))) {
					int w = v ^ (1 << pp[it->FT]) ^ (1 << pp[it->SD]);
					if (x[w] <= i) {
						x[w] = i + 1;
						q.push(w);
						rr = (rr + 1) % mod;
					}
				}
			}
		}
		r = (LL(r) * rr) % mod;
	}
	printf("%d\n", r);
}