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
// Kacper Orszulak
#ifndef DEBUG
    #define NDEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvll = vector<vll>;
#define st first
#define nd second
#define pb push_back
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define whole(x) x.begin(), x.end()
[[maybe_unused]] constexpr int INF = 1e9+7;
template<class T> bool minR(T &a, const T &b) {
	if (b < a) { a = b; return true; }
	else return false;
}
template<class T> bool maxR(T &a, const T &b) {
	if (b > a) { a = b; return true; }
	else return false;
}
constexpr ll MOD = 1e9+7;

int n, m;
vb startStateArr;
vector<pii> switches;

bool getBit(ll mask, int id) {
    return (mask & (1ll<<id)) >> id;
}

inline ll switchBit(ll mask, int id) {
    return mask ^ (1ll << id);
}

inline ll switchBits(ll mask, int a, int b) {
    return switchBit(switchBit(mask, a), b);
}

void printState(ll state) {
    rep(i, n) {
        cerr << (state & 1);
        state >>= 1;
    }
    cerr << '\n';
}

namespace Brute {
    vb stateAccessible;

    void brute() {
        cerr << "BRUTE\n";

        stateAccessible.resize(1<<n, false);

        ll startState = 0;
        rep(i, n) {
            startState |= (ll(startStateArr[i]) << i);
        }

        ll accessibleStatesCnt = 1;

        vll nextState;
        nextState.push_back(startState);
        stateAccessible[startState] = true;

        while (not nextState.empty()) {
            const ll state = nextState.back();
            nextState.pop_back();
#ifdef DEBUG
            printState(state);
#endif // DEBUG

            for (const auto &[a, b] : switches) {
                if (getBit(state, a) != getBit(state, b))
                    continue;
                const ll newState = switchBits(state, a, b);
                if (stateAccessible[newState])
                    continue;
                stateAccessible[newState] = true;
                nextState.push_back(newState);
                ++accessibleStatesCnt;
            }
        }

#ifdef DEBUG
        // rep(state, 1<<n) {
        //     if (not stateAccessible[state])
        //         continue;
        //     printState(state);
        // }
#endif // DEBUG

        accessibleStatesCnt %= MOD;
        cout << accessibleStatesCnt << '\n';
    }
}

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

    cin >> n >> m;
    startStateArr.resize(n, false);
    switches.resize(m);

    rep(i, n) {
        bool b; cin >> b;
        startStateArr[i] = b;
    }
    for (auto &[a, b] : switches) {
        cin >> a >> b;
        --a; --b;
    }

#ifdef SOL
#elif defined BRUTE
    Brute::brute();
#else
    Brute::brute();
#endif
}