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
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define inf 1e18
using namespace std;
using ll = long long;
using ld = long double;
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){return os <<"("<< m.first<<", "<<m.second<<")";}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){os<<"{";for(int i=0; i<(int)V.size(); i++){if(i)os<<" ";os<<V[i];}os<<"}" << endl;return os;}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int losuj(int a, int b){return rng()%(b-a+1)+a;}

#define rozmiar 2000100
#define mod 1000000007
#define int long long

int n, m, c[rozmiar], a, b, kolor[rozmiar];long long ile1_a, ile1_b, ile2_a, ile2_b;
vector<int> graf[rozmiar];
bool visited[rozmiar], czydwudzielny;
vector<int> spojne;
long long silnie[rozmiar], odp, czasowy;

void dfs(int k){
    visited[k]=1;
    for(int i:graf[k])if(!visited[i])dfs(i);
}

long long szybpot(long long c, long long d){
    if(d==0)return 1;
    if(d%2==0){
        long long o=szybpot(c, d/2);
        return (o*o)%mod;
    }
    return (c*szybpot(c, d-1))%mod;
}

long long odwr(long long c){
    return szybpot(c, mod-2);
}

long long npok(long long m, long long l){
    return (((silnie[m]*odwr(silnie[l]))%mod)*odwr(silnie[m-l]))%mod;
}

void koloruj(int k){
    visited[k]=1;
    if(kolor[k]==1 && c[k]==0)ile1_a++;
    if(kolor[k]==2 && c[k]==0)ile2_a++;
    if(kolor[k]==1 && c[k]==1)ile1_b++;
    if(kolor[k]==2 && c[k]==1)ile2_b++;
    for(int i:graf[k]){
        if(kolor[i]!=0 && kolor[i]==kolor[k])czydwudzielny=0;
        kolor[i]=3-kolor[k];
        if(!visited[i])koloruj(i);
    }
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> c[i];
    for(int i=0;i<m;i++){
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            spojne.push_back(i);
            dfs(i);
        }
    }
    silnie[0]=1;
    for(int i=1;i<=n;i++){
        silnie[i]=(silnie[i-1]*i)%mod;
    }
    odp=1;
    for(int i=1;i<=n;i++)visited[i]=0;
    for(auto i:spojne){
       // cout << i << endl;
        czydwudzielny=1;
        kolor[i]=1;
        ile1_a=0;
        ile2_a=0;
        ile1_b=0;
        ile2_b=0;
        koloruj(i);
        //cout << czydwudzielny << " " << ile1_a << ile1_b << ile2_a << ile2_b << endl;
        //cout << odp << endl;
        if(czydwudzielny){
            czasowy=0;
            int x=ile1_a, y=ile1_b, z=ile2_a, q=ile2_b;
            while(x>=0 && z>=0 && y<=ile1_a+ile1_b && q<=ile2_a+ile2_b){
                czasowy+=(npok(x+y, x)*npok(z+q, z));
                czasowy%=mod;
                x--;
                z--;
                y++;
                q++;
            }
            x=ile1_a+1, y=ile1_b-1, z=ile2_a+1, q=ile2_b-1;
            while(y>=0 && q>=0){
                czasowy+=(npok(x+y, x)*npok(z+q, z));
                czasowy%=mod;
                x++;
                z++;
                y--;
                q--;
            }
            odp*=czasowy;
            odp%=mod;
        }else{
            odp*=szybpot(2, ile1_a+ile1_b+ile2_a+ile2_b-1);
            odp%=mod;
        }
    }
    cout << odp << endl;
    return 0;
}