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

using namespace std;

struct wierzcholek{
    bool zapalony;
    bool zbior;
    bool odwiedzony = false;
    vector<int>krawedzie;
};

long long pot(int wykladnik, long long podstawa);
long long dwumian(long long k, long long n, vector<long long>&silnie, vector<long long>&potegi);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,a,b;
    long long wynik=1,dowyniku;
    cin >> n >> m;
    vector<wierzcholek>v(n+1);
    for(int i=1; i<=n; i++){
        cin >> v[i].zapalony;
    }
    for(int i=0; i<m; i++){
        cin >> a >> b;
        v[a].krawedzie.push_back(b);
        v[b].krawedzie.push_back(a);
    }
    int w;
    bool klika;
    int wielkosc,dolny,gorny; // dolny i gorny bound na liczbe jedynek w zbiorze 0
    vector<vector<int>>z(2,vector<int>(2)); // odpowiednio zbior i liczba zer/jedynek
    vector<long long>silnie(n+1);
    vector<long long>potegi(n+1);
    silnie[1]=1;
    potegi[1]=1;
    for(int i=2; i<=n; i++){
        silnie[i]=(silnie[i-1]*i)%1000000007;
        potegi[i] = pot(1000000005,silnie[i]);
    }
    for(int i=1; i<=n;i++){
        if(!v[i].odwiedzony){
            wielkosc = 0;
            z[0][0] = 0;
            z[0][1] = 0;
            z[1][0] = 0;
            z[1][1] = 0;
            klika = false;
            v[i].odwiedzony = true;
            v[i].zbior = true;
            queue<int>kolejka;
            kolejka.push(i);
            while(!kolejka.empty()){
                w = kolejka.front();
                z[v[w].zbior][v[w].zapalony]++;
                wielkosc++;
                kolejka.pop();
                for(int j=0; j<v[w].krawedzie.size();j++){
                    if(!v[v[w].krawedzie[j]].odwiedzony){
                        v[v[w].krawedzie[j]].odwiedzony = true;
                        v[v[w].krawedzie[j]].zbior = (!v[w].zbior);
                        kolejka.push(v[w].krawedzie[j]);
                    }else{
                        if(v[v[w].krawedzie[j]].zbior == v[w].zbior){
                            klika = true;
                        }
                    }
                }
            }
            if(klika){
                wynik = (wynik*pot(wielkosc-1,2))%1000000007;
                if(wynik<0)wynik+=1000000007;
                if(wynik == 1000000007){
                    cout << "0" << endl;
                    return 0;
                }
            }else{
                if(wielkosc>1){
                    dowyniku = 0;
                    dolny = max(z[0][1] - z[1][1],0);
                    gorny = z[0][1] + min(z[1][0],z[0][0]);
                    for(int j=dolny; j<=gorny; j++){
                        dowyniku = (dowyniku+(dwumian(j,z[0][0]+z[0][1],silnie,potegi)*dwumian(z[0][1]+z[1][0]-j,z[1][0]+z[1][1],silnie,potegi)))%1000000007;
                    }
                    wynik = (wynik*dowyniku)%1000000007;
                }
            }
        }
    }
    cout << wynik << endl;
    return 0;
}

long long pot(int wykladnik, long long podstawa){
    if(wykladnik==0)return 1;
    long long wynik;
    if(wykladnik%2==0){
        wynik = pot(wykladnik/2,podstawa);
        return ((wynik*wynik)%1000000007);
    }else{
        wynik = pot((wykladnik-1)/2, podstawa);
        return (((wynik*wynik)%1000000007)*podstawa)%1000000007;
    }
}

long long dwumian(long long k, long long n, vector<long long>&silnie, vector<long long>&potegi){
    if(k==0 || n==k)return 1;
    long long wynik = (((silnie[n]*potegi[n-k])%1000000007)*potegi[k])%1000000007;
    return wynik;
}