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
#include <bits/stdc++.h>
using std::cin, std::cout, std::vector;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#define REP(i, n) for (u32 i=0; i<(n); ++i)

void init_io() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

template<class T>
T power(T a, unsigned b) {
  T res = T(1);
  while(b) {
    if(b&1u) res *= a;
    b >>= 1;
    a = a*a;
  }
  return res;
}

template<unsigned MOD>
class Modulo {
public:
  Modulo(unsigned x=0):v(x) {}
  unsigned get() const { return v; }
  Modulo operator+(Modulo b) const {
    unsigned res = v+b.v;
    if (res >= MOD) res -= MOD;
    return res;
  }
  void operator+=(Modulo b) { *this = *this + b; }
  Modulo operator-(Modulo b) const { return *this + Modulo(MOD-b.v); }
  void operator-=(Modulo b) { *this = *this - b; }
  Modulo operator*(Modulo b) const { return Modulo(std::uint64_t(v) * b.v % MOD); }
  void operator*=(Modulo b) { *this = *this * b; }
  Modulo operator/(Modulo b) const { return *this * b.inverse(); }
  void operator/=(Modulo b) { *this = *this / b; }
  Modulo inverse() const { return power(*this, MOD-2); }
private:
  unsigned v;
};

// ===================

using Mod = Modulo<1'000'000'007>;

constexpr u8 unvisited = 0xff;

Mod factorial(const u32 n) {
  Mod res = 1;
  for (u32 i=1; i<=n; ++i) {
    res *= i;
  }
  return res;
}

struct Node {
  u32 color = 0;
  u32 parity = unvisited;
  vector<u32> edges;
};

class Graph {
public:
  void read() {
    u32 num_edges;
    cin >> num_nodes >> num_edges;
    nodes.resize(num_nodes);
    for (Node &node:nodes) cin >> node.color;
    REP(i, num_edges) {
      u32 a, b;
      cin >> a >> b;
      --a; --b;
      nodes[a].edges.push_back(b);
      nodes[b].edges.push_back(a);
    }
    bfs_queue.reserve(num_nodes);
  }

  Mod count_configurations() {
    Mod p = 1, q = 1;
    REP(i, num_nodes) {
      if (nodes[i].parity == unvisited) {
        const auto [a, b] = count_component(i);
        p *= a;
        q *= b;
      }
    }
    return p / q;
  }

  std::pair<Mod, Mod> count_component(const u32 start) {
    bool bipartite = true;
    nodes[start].parity = 0;
    bfs_queue = {start};
    u32 counts[2] = {};
    for (u32 i=0; i<bfs_queue.size(); ++i) {
      const u32 x = bfs_queue[i];
      counts[nodes[x].parity ^ nodes[x].color] += 1;
      for (const u32 y : nodes[x].edges) {
        if (nodes[y].parity == unvisited) {
          nodes[y].parity = nodes[x].parity ^ 1;
          bfs_queue.push_back(y);
        } else if (nodes[y].parity == nodes[x].parity) {
          bipartite = false;
        }
      }
    }
    if (bipartite) {
      return {factorial(counts[0] + counts[1]), factorial(counts[0]) * factorial(counts[1])};
    } else {
      return {power(Mod(2), counts[0] + counts[1] - 1), Mod(1)};
    }
  }

private:
  u32 num_nodes;
  vector<Node> nodes;
  vector<u32> bfs_queue;
};

int main() {
  init_io();

  Graph graph;
  graph.read();
  const auto res = graph.count_configurations();
  cout << res.get() << "\n";
}