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
#include <ios>
#include <functional>
#include <cassert>
#include <vector>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define SREP(n) REP(_ ## n, n)
#define FOR(i, p, n) for(int i=(p); i<=(n); ++i)
#define RFOR(i, p, n) for(int i=(p); i>=(n); --i)
#define pb push_back
#define eb emplace_back
#define C const
#define V std::vector
#define F std::function
#define R std::ranges
#define RV std::ranges::views
#define sz(A) int(A.size())
#define all(A) A.begin(), A.end()
#define rall(A) A.rbegin(), A.rend()
typedef long long ll;
typedef long double ld;
typedef V <int> vi;
typedef V <vi> vvi;
typedef V <bool> vb;
typedef V <char> vc;
typedef V <ll> vll;
typedef const int ci;
typedef const ll cll;
int I(){
    int z;
    while ((z=getchar_unlocked())<'0'||z>'9');
    int r=z-'0';
    while ((z=getchar_unlocked())>='0'&&z<='9')
        r=r*10+z-'0';
    return r;
}
ci MOD=1e9+7;
ll poteg(ll a, ll w){
    ll r=1;
    for (; w; w>>=1,a=a*a%MOD)
        if (w&1)
            r=r*a%MOD;
    return r;
}
int main(){
    ci n=I(),m=I();
    vll sil(n+1),odwr(n+1);
    sil[0]=1;
    FOR(i, 1, n)
        sil[i]=sil[i-1]*i%MOD;
    odwr[n]=poteg(sil[n], MOD-2);
    RFOR(i, n, 1)
        odwr[i-1]=odwr[i]*i%MOD;
    auto dwum=[&](ci a, ci b) -> ll{
        return sil[a]*odwr[b]%MOD*odwr[a-b]%MOD;
    };
    vvi pol(n);
    vi stan(n);
    REP(i, n)
        stan[i]=I();
    SREP(m){
        ci p=I()-1,k=I()-1;
        pol[p].eb(k);
        pol[k].eb(p);
    }
    vi odw(n),gl(n);
    ll w=1;
    REP(s, n)
        if (!odw[s]){
            bool czyniep=0;
            static int ilegl[2],ileglzap[2];
            ilegl[0]=ilegl[1]=ileglzap[0]=ileglzap[1]=0;
            F <void(ci)> dfs=[&](ci i){
                odw[i]=1;
                ++ilegl[gl[i]];
                ileglzap[gl[i]]+=stan[i];
                for (ci j : pol[i]){
                    if (!odw[j])
                        gl[j]=gl[i]^1,dfs(j);
                    else if (gl[i]^gl[j]^1)
                        czyniep=1;
                }
            };
            dfs(s);
            if (czyniep){
                ci rozm=ilegl[0]+ilegl[1],zappar=(ileglzap[0]+ileglzap[1])&1;
                ll l=0;
                for (int a=zappar; a<=rozm; a+=2)
                    l=(l+dwum(rozm, a))%MOD;
                w=w*l%MOD;
            }
            else{
                ci d=abs(ileglzap[0]-ileglzap[1]);
                if (ileglzap[0]<ileglzap[1])
                    std::swap(ilegl[0], ilegl[1]);
                ll l=0;
                FOR(ile0, d, ilegl[0]){
                    ci ile1=ile0-d;
                    if (ile1>ilegl[1])
                        break;
                    l=(l+dwum(ilegl[0], ile0)%MOD*dwum(ilegl[1], ile1))%MOD;
                }
                w=w*l%MOD;
            }
        }
    printf("%lld\n", w);
}