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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
ll ile=0;
map<vector<bool>,bool>czy;
void q(vector<bool>&a,vector<pair<int,int>>&b,int &m,vector<bool>&o,int rr)
{
    if(czy[a] && rr)
    {
        return;
    }
    czy[a]=true;
    ile=(ile+1)%1000000007;
    for(int i=0;i<m;i++)
    {
        if(a[b[i].st]==a[b[i].nd] && o[b[i].st])
        {
            a[b[i].st]=!a[b[i].st];
            a[b[i].nd]=!a[b[i].nd];
            q(a,b,m,o,1);
            a[b[i].st]=!a[b[i].st];
            a[b[i].nd]=!a[b[i].nd];
        }
    }
}
void ww(vector<vector<int>>&c,vector<bool>&d,int i,vector<bool>&o)
{
    if(d[i])
    {
        return;
    }
    d[i]=true;
    o[i]=true;
    for(int j=0;j<c[i].size();j++)
    {
        ww(c,d,c[i][j],o);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
   int n,m;
   cin>>n>>m;
   vector<bool>a(n);
   vector<pair<int,int>>b(m);
   for(int i=0;i<n;i++)
   {
        int o;
        cin>>o;
        if(o)
        {
            a[i]=true;
        }
   }
   vector<vector<int>>c(n);
   for(int i=0;i<m;i++)
   {
        cin>>b[i].st>>b[i].nd;
        b[i].st--;
        b[i].nd--;
        c[b[i].st].push_back(b[i].nd);
        c[b[i].nd].push_back(b[i].st);
   }
    ll wyn=1;
    vector<bool>d(n);
    for(int i=0;i<n;i++)
    {
        if(!d[i])
        {
            ile=0;
            vector<bool>o(n);
            ww(c,d,i,o);
            q(a,b,m,o,0);
            wyn*=ile;
            wyn%=1000000007;
        }
    }
    cout<<wyn%1000000007<<endl;
}