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
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int mod = 1e9 + 7;
struct Mint {
  int val;
  Mint(ll x = 0): val((x % mod + mod) % mod) {;}
  Mint operator +(const Mint& x) { return Mint(val + x.val); }
  Mint operator -(const Mint& x) { return Mint(val - x.val); }
  Mint operator *(const Mint& x) { return Mint((ll)val * x.val); }
  Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
  Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
  Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
  Mint operator ^(const int& _b) const {
    Mint accum = 1, a = *this;
    int b = _b;
    while(b) {
      accum = (b & 1? accum * a : accum);
      a *= a;
      b >>= 1;
    }
    return accum;
  }
  Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
  Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};

namespace COMBI {
  const int nmax = 2e5 + 5;  
  Mint fact[nmax], invfact[nmax];
  void init(int n = nmax - 1) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    invfact[n] = Mint(1) / fact[n];
    for(int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * Mint(i);
    return;
  }
  Mint f(int n) { return fact[n]; }
  Mint invf(int n) { return invfact[n]; }
  Mint ncr(int n, int r) { return fact[n] * invfact[r] * invfact[n - r]; }
}

const int nmax = 2e5 + 5;

int light[nmax];
int atrcol[nmax];

vector<int> g[nmax];

bool bipartit = 1;
int cnt[2] = {0, 0};

void checkbip(int node, int trial) {
   if(atrcol[node] != 0) {
      if(atrcol[node] != trial) bipartit = 0;
      return;
   }
   cnt[0]++;
   if((light[node] ^ (trial - 1)) == 1) cnt[1]++;
   atrcol[node] = trial;
   for(auto x : g[node])
      checkbip(x, 3 - trial);
   return;
}

signed main() {
   COMBI::init();
   cin.tie(0) -> sync_with_stdio(0);
   int n, m;
   cin >> n >> m;

   for(int i = 1; i <= n; i++) cin >> light[i];

   for(int x, y, i = 1; i <= m; i++) {
     cin >> x >> y;
     
     g[x].emplace_back(y);
     g[y].emplace_back(x);
   }

   Mint total = 1;

   for(int i = 1; i <= n; i++) {
      if(atrcol[i] == 0) {
         bipartit = 1;
         cnt[0] = cnt[1] = 0;
         checkbip(i, 1);
         
         //cerr << i << '\t' << cnt[0] << ' ' << cnt[1] << '\n';
         
         if(bipartit == 0)
            total *= Mint(2) ^ (cnt[0] - 1);
         else
            total *= COMBI::ncr(cnt[0], cnt[1]);
      }
   }
   
   cout << total.val << '\n';


}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/