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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

vector<int> edges[200001];
int vertex_parity[200001]; // 0, 1, 2=unknown
int blackness[200001];
int factorials[200001];

struct nextthing{
    int x;
    int parity;
};

void all_factorials(int n) {
    long long res = 1;
    factorials[0] = 1;
    factorials[1] = 1;
    for (int i = 2; i <= n; ++i) {
        res *= i;
        res %= 1'000'000'007LL;
        factorials[i] = int(res);
    }
}

long long odw_modulo(long long k) {
    long long r = 1'000'000'007LL;
    long long newr = k;
    long long t = 0;
    long long newt = 1;
    long long temp;

    while (newr != 0) {
        long long quotient = r / newr;
        temp = newt;
        newt = t - (quotient * newt);
        t = temp;

        temp = newr;
        newr = r - (quotient * newr);
        r = temp;
    }

    while (t < 0) {
        t += 1'000'000'007LL;
    }
    return t;
}

long long binomial(int n, int k) {
//    printf("COMPUTING BINOMIAL n choose k\n");
    long long res = factorials[n];
    long long lowpart = factorials[k];
    lowpart *= factorials[n-k];
    lowpart %= 1'000'000'007LL;
//    printf("n! = %lld\n", res);
//    printf("k! * (n-k)! = %lld\n", lowpart);
    res *= odw_modulo(lowpart);
    res %= 1'000'000'007LL;
//    printf("RESULT: %lld\n", res);
    return res;
}

long long process_component(int x, int parity) {
    queue<nextthing> stuff;
    int counts[2][2]; // counts[a][b] = number of a color in b parity
    counts[0][0] = 0;
    counts[0][1] = 0;
    counts[1][0] = 0;
    counts[1][1] = 0;
    int component_size = 0;
    bool everything = false;

    nextthing firstthing;
    firstthing.x = x;
    firstthing.parity = parity;
    vertex_parity[x] = parity;
    stuff.push(firstthing);

    while (!stuff.empty()) {
        nextthing topstuff = stuff.front();
        stuff.pop();
        int current_parity = topstuff.parity;
        counts[blackness[topstuff.x]][current_parity]++;
        component_size++;
        for (int i = 0; i < edges[topstuff.x].size(); ++i) {
            int n = edges[topstuff.x][i];
            if (vertex_parity[n] == 2) {
                int n_parity = 1 - current_parity;
                nextthing newthing;
                newthing.x = n;
                newthing.parity = n_parity;
                vertex_parity[n] = n_parity;
                stuff.push(newthing);
            } else if (vertex_parity[n] == current_parity) {
                // nothing is true, everything is permitted
                everything = true;
                // don't break cause we still need to know component size
            }
        }
    }

    if (component_size == 1) {
//        printf("SIZE 1 COMPONENT\n");
        // just to remove the "what if one partition is empty" headache
        return 1;
    }

    if (everything) {
//        printf("EVERYTHING COMPONENT ");
        // return 2^(n-1) where n is component size
        // i guess we can just compute it in O(n) cause it will amortize
        int result = 1;
        for (int i = 1; i < component_size; ++i) {
            result *= 2;
            result %= 1'000'000'007;
        }
//        printf("OF RESULT %d (SIZE %d)\n", result, component_size);
        return result;
    } else {
//        printf("BIPARTITE COMPONENT\n");
        // graph is bipartite.
        // 1. compute whiteness ranges
        // 2. compute possibility quotients

        int maxwhites[2]; // max number of 0s in x parity
        int minwhites[2]; // min number of 0s in x parity
        int parity_total[2]; // total vertices in x parity

        parity_total[0] = counts[0][0] + counts[1][0];
        parity_total[1] = counts[0][1] + counts[1][1];

        // turn all to black - counts[0][x] is now minimum number of 0s in x parity
        int convertible_whites = min(counts[0][0], counts[0][1]);
        counts[1][0] += convertible_whites;
        counts[0][0] -= convertible_whites;
        counts[1][1] += convertible_whites;
        counts[0][1] -= convertible_whites;

        minwhites[0] = counts[0][0];
        minwhites[1] = counts[0][1];

        // now turn all to white
        int convertible_blacks = min(counts[1][0], counts[1][1]);

        maxwhites[0] = counts[0][0] + convertible_blacks;
        maxwhites[1] = counts[0][1] + convertible_blacks;

        long long result = 0;

        int range = maxwhites[0] - minwhites[0];

        // sum of all over whites foreach possible white range
        for(int i = 0; i <= range; ++i) {
//            printf("LEFTSIDE : %2d whites out of %2d total\n", i+minwhites[0], parity_total[0]);
//            printf("RIGHTSIDE: %2d whites out of %2d total\n", i+minwhites[1], parity_total[1]);
            long long leftside = binomial(parity_total[0], i + minwhites[0]);
            long long rightside = binomial(parity_total[1], i + minwhites[1]);
            result += leftside * rightside;
            result %= 1'000'000'007;
//            printf("ADDING %lld TO RESULT FOR %lld TOTAL\n", leftside * rightside, result);
        }


        return result;
    }
}

int main() {
    /* ODW_MODULO TESTS
    printf("%lld %lld\n", odw_modulo(1), odw_modulo(2));
    for (int i = 1; i < 1'000'000'007; ++i) {
        long long z = odw_modulo(i);
        long long myown = (i * z) % 1'000'000'007;
        if (myown != 1) {
            printf("ERROR FOR %d  !\n", i);
        }
        if (i % 10'000'000 == 0){
            printf("%10d\n", i);
        }
    }
    printf("All done\n");
    return 0;
    /* END OF ODW_MODULO TESTS */
    /* BINOMIAL TESTS
    all_factorials(100);

    printf("%3d\n", binomial(1, 1));
    printf("%3d %3d\n", binomial(2, 1), binomial(2, 2));
    printf("%3d %3d %3d\n", binomial(3, 1), binomial(3, 2), binomial(3, 3));
    printf("%3d %3d %3d %3d\n", binomial(4, 1), binomial(4, 2), binomial(4, 3), binomial(4, 4));
    printf("%3d %3d %3d %3d %3d\n", binomial(5, 1), binomial(5, 2), binomial(5, 3), binomial(5, 4), binomial(5, 5));
    printf("%3d %3d %3d %3d %3d %3d\n", binomial(6, 1), binomial(6, 2), binomial(6, 3), binomial(6, 4), binomial(6, 5), binomial(6, 6));
    return 0;
    /* END OF BINOMIAL TESTS */
    int n, m;
    scanf("%d %d", &n, &m);
    all_factorials(n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        blackness[i] = x;
        vertex_parity[i] = 2;
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }

    long long total_result = 1;

    for(int i = 0; i < n; ++i) {
        if (vertex_parity[i] == 2) {
//            printf("COMPUTING %d COMPONENT\n", i);
            long long result = process_component(i, 0);
            total_result *= result;
            total_result %= 1'000'000'007;
        }
    }

    printf("%lld\n", total_result);

    return 0;
}