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
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long
using namespace std;
template<class T,int N>struct Dinic{
    const T INF=numeric_limits<T>::max()/2;
    int n,s,t,h[N],d[N];
    vector<tuple<int,T,int>>G[N];
    inline void add(const int&u,const int&v,const T&w){
        if(u!=v){
            const int ru=G[v].size(),rv=G[u].size();
            G[u].emplace_back(v,w,ru),G[v].emplace_back(u,0,rv);
        }
    }
    inline bool bfs(){
        int ql=0,qr=1;static int Q[N];
        for(fill(d+1,d+n+1,-1),d[Q[1]=s]=0;ql<qr;){
            int u=Q[++ql];h[u]=0;if(u==t)return 1;
            for(auto [v,w,_]:G[u])if(w&&d[v]<0)d[Q[++qr]=v]=d[u]+1;
        }
        return 0;
    }
    inline T dfs(const int&u,T mf){
        if(u==t)return mf;
        T z=0;
        for(int&i=h[u];i<G[u].size();++i){
            const auto [v,w,j]=G[u][i];
            if(d[u]+1==d[v]&&w){
                const T dd=dfs(v,min(mf,w));
                get<1>(G[u][i])-=dd,mf-=dd,get<1>(G[v][j])+=dd,z+=dd;
                if(!mf)return z;
            }
        }
        return d[u]=-1,z;
    }
    inline void init(const int&_n,const int&_s,const int&_t){
        n=_n,s=_s,t=_t;for(int i=1;i<=n;++i)G[i].clear();
    }
    inline T flow(){T z=0;while(bfs())z+=dfs(s,INF);return z;}
};
const int N=2e5+5,P=1e9+7;
int n,m,ans=1;Dinic<int,N>Gr;
int c[N],vs[N],col[N],id[N],frc[N],ivf[N];vector<int>vec,G[N];
inline int qpow(int x,int y,int z=1){for(;y;(y>>=1)&&(x=1ll*x*x%P))if(y&1)z=1ll*z*x%P;return z;}
inline int binom(const int&n,const int&m){
    return m<0||n<m?0:1ll*frc[n]*ivf[m]%P*ivf[n-m]%P;
}
inline void dfs(int u){
    vec.emplace_back(u),vs[u]=1;
    for(auto v:G[u])if(!vs[v])dfs(v);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m,frc[0]=1;
    for(int i=1;i<=n;++i)frc[i]=1ll*frc[i-1]*i%P;
    ivf[n]=qpow(frc[n],P-2);
    for(int i=n;i;--i)ivf[i-1]=1ll*i*ivf[i]%P;
    for(int i=1;i<=n;++i)cin>>c[i],col[i]=-1;
    for(int i=1;i<=m;++i){
        int u,v;cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    for(int i=1;i<=n;++i)if(!vs[i]){
        vec.clear(),dfs(i);bool ok=1;
        int cnt=0,s[2][2];s[0][0]=s[0][1]=s[1][0]=s[1][1]=0;
        for(auto u:vec){
            if(col[u]==-1)col[u]=c[u];id[u]=++cnt;++s[col[u]][c[u]];
            for(auto v:G[u])if(col[v]==-1)col[v]=!col[u];else if(col[v]==col[u]){ok=0;break;}
        }
        if(!ok){ans=qpow(2,vec.size()-1,ans);continue;}
        Gr.init(cnt+2,cnt+1,cnt+2);
        for(auto u:vec)
            if(!col[u]){
                Gr.add(cnt+1,id[u],1);
                for(auto v:G[u])Gr.add(id[u],id[v],1);
            }
            else Gr.add(id[u],cnt+2,1);
        int mf=Gr.flow(),cur=0;
        for(int i=-min(s[0][1],s[1][1]);i<=min(s[0][0],s[1][0]);++i)
            if(abs(i)<=mf)cur=(cur+1ll*binom(s[0][0]+s[0][1],s[0][1]+i)*binom(s[1][0]+s[1][1],s[1][1]+i))%P;
        ans=1ll*ans*cur%P;
    }
    return cout<<ans,0;
}
/*
*/