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
#include <iostream>
#include <vector>
using namespace std;

const long long mod=1'000'000'007;

vector<long long> tab[500'007];
long long byo[500'007];
long long zap[500'007];
long long parz[500'007];
long long silnia[500'007];
long long jed, dwa, cykl, zmia;

void dfs(long long v, long long h)
{
    if(byo[v]!=0 && byo[v]!=h)
        cykl=1;
    if(byo[v]!=0)
        return;
    byo[v]=h;
    //cout<<v<<" "<<h<<"\n";
    if(h==1)
        jed++;
    if(h==2)
        dwa++;
    if(h==1 && zap[v]==1)
        zmia++;
    if(h==2 && zap[v]==1)
        zmia--;
    for(int a=0; a<tab[v].size(); a++)
        dfs(tab[v][a], h%2+1);
}


long long pot(long long a, long long p)
{
    if(p==1)
        return a;
    long long wyk=pot(a, p/2);
    if(p%2==0)
        return (wyk*wyk)%mod;
    return ( ((wyk*wyk)%mod) *a)%mod;
}

long long odw(long long i)
{
    return pot(i%mod, mod-2);
}

long long becz(long long n, long long k)
{
    return (silnia[n]*odw(silnia[k]*silnia[n-k]))%mod;
}

int main()
{
    long long n, p, p2, odp=1, m, pom;
    cin>>n>>m;
    silnia[0]=1;
    for(long long a=1; a<=n+5; a++)
        silnia[a]=(silnia[a-1]*a)%mod;
    for(int a=1; a<=n; a++)
        cin>>zap[a];
    for(int a=0; a<m; a++)
    {
        cin>>p>>p2;
        tab[p].push_back(p2);
        tab[p2].push_back(p);
    }
    for(int a=1; a<=n; a++)
    {
        jed=0;dwa=0;cykl=0;zmia=0;pom=0;
        if(byo[a]==0 && tab[a].size()>0)
        {
            dfs(a,1);
            //cout<<"cykl "<<cykl<<" jed "<<jed<<" dwa "<<dwa<<" zmia "<<zmia<<"\n";
            if(cykl==1)
                pom=(pom+pot(2, jed+dwa-1))%mod;
            else
            {
                if(zmia<0)
                    zmia=zmia*-1;
                else
                    swap(jed,dwa);
                for(long long i=0; i+zmia<=dwa && i<=jed; i++)
                    pom=(pom+ (becz(dwa,i+zmia)*becz(jed,i))%mod )%mod;
            }
            odp=(odp*pom)%mod;
            //cout<<odp<<"\n";
        }
    }
    cout<<odp<<"\n";
}