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
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>

//#define __DEBUG

#define REP(x,n) for (int x=0;x<(n);++x)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())
#ifdef __DEBUG
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif

using namespace std;

void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

#define MAX_N 200001
#define MAX_M 400001
#define MOD 1000000007LL
short input[MAX_N];
pair<int,int> switches[MAX_M];

struct Vertex {
    set<int> e;
    int groupNo;
};
struct Graph {
    vector<Vertex> v;
} graph;

/** returns number of vertices in group **/
int makeDFS(int vertex, int groupNo, bool* hasAnyValidLink) {
    graph.v[vertex].groupNo = groupNo;
    short thisInput = input[vertex];
    
    int count = 1;
    FOREACH(it, graph.v[vertex].e) {
        if (graph.v[*it].groupNo == 0) {
            count += makeDFS(*it, groupNo, hasAnyValidLink);
        }
        if (input[*it] == thisInput) {
            *hasAnyValidLink = true;
        }
    }
    return count;
}

long long pow2(int exp) {
    if (exp == 0) {
        return 1LL;
    }
    long long result = pow2(exp/2);
    result *= result;
    if (exp & 1) {
        result *= 2;
    }
    return result % MOD;

}

void solve() {
    int n,m,ai,bi;
    cin>>n>>m;
    graph.v.resize(n+1);
    REP(x,n)
        cin>>input[x+1];
    REP(x,m) {
        cin >> ai >> bi;
        graph.v[ai].e.insert(bi);
        graph.v[bi].e.insert(ai);
    }
    int groupNo = 0;
    long long result = 1;
    REP(x,n) {
        if (graph.v[x+1].groupNo == 0) {
            bool hasAnyValidLink = false;
            int count = makeDFS(x+1, ++groupNo, &hasAnyValidLink);
            if (hasAnyValidLink) {
                DEBUG(cerr << "group of " << count << " added to score" << endl;)
                result = (result * pow2(count-1)) % MOD;
            } else {
                DEBUG(cerr << "group of " << count << " not added to score" << endl;)
            }
        }
    }
    cout << result;
}