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
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>

int n, m;
std::vector<int> t;
std::vector< std::unordered_set<int> > g;
const long long mod = 1'000'000'007;

void input() {
    std::cin >> n >> m;
    int x;
    for (int i = 0; i < n; i++) {
        std::cin >> x;
        t.push_back(x);
        g.push_back(std::unordered_set<int>());
    }

    int u, v;
    for (int i = 0; i < m; i++) {
        std::cin >> u >> v;
        u--;
        v--;
        g[u].insert(v);
        g[v].insert(u);
    }
}

long long pow_mod(long long base, long long exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return base;
    }
    if (exp % 2 == 1) {
        return (base * pow_mod(base, exp - 1)) % mod;
    }
    long long p = pow_mod(base, exp / 2);
    return (p * p)  % mod;
}

long long count(int u0, std::vector<bool> &visited) {
    std::queue<int> q;
    q.push(u0);

    bool has_cycle = false;
    bool equal_neighbours = false;
    int len = 0;

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

        if (visited[u]) {
            has_cycle = true;
            continue;
        }

        visited[u] = true;
        len++;

        for (auto v : g[u]) {
            if (t[u] == t[v]) {
                equal_neighbours = true;
            }

            if (visited[v]) {
                continue;
            }

            q.push(v);
        }
    }

//    std::cout << u0 << " " << has_cycle << " " << equal_neighbours << " " << len << "\n";

    if (has_cycle) {
        return pow_mod(2, len - 1);
    }
    if (equal_neighbours) {
        return len;
    }
    return 1;
}

void solve() {
    std::vector<bool> visited(n);
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }

    long long result = 1;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            result = (result * count(i, visited)) % mod;
        }
    }

    std::cout << result << "\n";
}

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

    input();
    solve();

    return 0;
}