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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>

using namespace std;

#define debug if (0)

typedef long long lld;

const lld MOD = 1e9 + 7;

int n, m;

lld fpw(lld x, lld k) {
  lld res = 1;
  for (; k > 0; k >>= 1, x = x * x % MOD)
    if (k & 1)
      res = res * x % MOD;
  return res;
}

struct component {
  int sz = 0;
  bool bipartite = true;
  pair<int, int> l, r;
};

component make_component(const vector<vector<int>> &v, vector<int> &visited,
                         const vector<int> &col, int start) {
  component res;

  queue<int> q;
  visited[start] = 1;
  q.push(start);
  res.sz++;
  res.l.first++;
  res.l.second += col[start];

  while (!q.empty()) {
    int x = q.front();
    q.pop();

    for (int u : v[x]) {
      if (visited[u] == visited[x])
        res.bipartite = false;
      if (visited[u] != 0)
        continue;

      visited[u] = 3 - visited[x];
      q.push(u);
      pair<int, int> &part = (visited[u] == 1 ? res.l : res.r);
      res.sz++;
      part.first++;
      part.second += col[u];
    }
  }
  return res;
}

vector<component> get_connected(const vector<vector<int>> &v,
                                const vector<int> &col) {
  vector<int> visited(n, 0);
  vector<component> cc;
  for (int i = 0; i < n; ++i)
    if (visited[i] == 0)
      cc.push_back(make_component(v, visited, col, i));
  return cc;
}

bool frozen(const vector<int> &cc, const vector<vector<int>> &v,
            const vector<int> &col) {
  for (const int x : cc)
    for (const int u : v[x])
      if (col[x] == col[u])
        return false;
  return true;
}

lld calc(const pair<int, int> &l, const pair<int, int> &r) {
  lld x = l.first, y = r.first;
  lld ldif = max(0, l.second - r.second);
  lld rdif = max(0, r.second - l.second);
  debug {
    cout << "CALC(" << x << ", " << y << " | " << ldif << ", " << rdif << ")\n";
  }

  int k1 = 0, k2 = 0;
  lld lbinom = 1, rbinom = 1;
  for (; k1 < ldif; ++k1)
    lbinom = lbinom * (x - k1) % MOD * fpw(k1 + 1, MOD - 2) % MOD;
  for (; k2 < rdif; ++k2)
    rbinom = rbinom * (y - k2) % MOD * fpw(k2 + 1, MOD - 2) % MOD;

  lld res = 0;
  for (; k1 <= x && k2 <= y; ++k1, ++k2) {
    res += lbinom * rbinom % MOD;
    if (res >= MOD)
      res -= MOD;
    lbinom = lbinom * (x - k1) % MOD * fpw(k1 + 1, MOD - 2) % MOD;
    rbinom = rbinom * (y - k2) % MOD * fpw(k2 + 1, MOD - 2) % MOD;
  }
  debug { cout << "CALCED: " << res << endl; }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;

  vector<int> init(n);
  for (int &i : init)
    cin >> i;

  vector<vector<int>> v(n);
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    v[--x].push_back(--y);
    v[y].push_back(x);
  }

  vector<component> components = get_connected(v, init);
  lld res = 1;

  for (auto &[sz, bip, l, r] : components) {
    debug { cout << "RES -> " << res << endl; }

    if (!bip) {
      res = res * fpw(2, sz - 1) % MOD;
      continue;
    }
    res = res * calc(l, r) % MOD;
  }
  cout << res << '\n';
}