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
#include<iostream>
#include<math.h>
#include<vector>

using namespace std;

long long modulo = pow(10,9)+7;

long long result = 1;
int n,m;
vector<int> graf[200100];

bool visited[200100];
int c[200100];

int group_array[200100];

int group_counter[2];
int black_counter[2];

bool is_odd;
int component_n;

void dfs(int v, int group) {
    component_n++;
    visited[v] = true;
    group_array[v] = group;
    group_counter[group] ++;
    black_counter[group] += c[v];
    
    for(int w : graf[v]) {
        if(visited[w]) {
            if(group_array[w] == group) is_odd = true;
            continue;
        }
        
        dfs(w, 1-group);
    }
}

long long power_of_two() {
    long long wynik = 1;
    for(int i=0;i<component_n-1;i++)
        wynik = (wynik*2)%modulo;
        
    return wynik;
}

long long binomial() {
    if(black_counter[0] < black_counter[1]) {
        swap(group_counter[0], group_counter[1]);
        swap(black_counter[0], black_counter[1]);
    }
    
    long long binomial[2][max(group_counter[0], group_counter[1])];
    binomial[0][0] = 1;
    binomial[1][0] = 1;
    
    for(int which = 0; which < 2; which++) {
        for(int i=1;i<=group_counter[which];i++) {
            binomial[which][i] = (binomial[which][i-1]*(group_counter[which]-i+1))/i;
            binomial[which][i] %= modulo;
            //cout<<"Dla "<<group_counter[which]<<" na "<<i<< " beczka to "<<binomial[which][i]<<endl;
        }
    }
    
    long long wynik = 0;
    int roznica = black_counter[0]-black_counter[1];
    
    for(int i=0;i<=group_counter[1];i++) {
        if(i + roznica > group_counter[0]) break;
        wynik += (binomial[0][i+roznica]*binomial[1][i]);
        //cout<<"Dla i="<<i<<" dodaliśmy "<<(binomial[0][i+roznica]*binomial[1][i])<<endl;
        wynik %= modulo;
    }
    
    //cout<<"wynik to "<<wynik<<endl;
    
    return wynik;
}

void testuj() {
    for(int i=1;i<=n;i++) c[i] = 1;
    
    for(int i=1;i<=m;i++) {
        graf[i].push_back(i+1);
        graf[i+1].push_back(i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    /*cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=0;i<m;i++) {
        int a,b;
        cin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }*/
    
    n = 200000;
    m = 199999;
    testuj();
    
    for(int i=1;i<=n;i++) {
        if(visited[i]) continue;
        
        for(int j=0;j<2;j++) {
            group_counter[j] = 0;
            black_counter[j] = 0;
        }
        
        is_odd = false;
        component_n = 0;

        dfs(i, 0);
        cout<<"a"<<endl;

        if(is_odd) //nieparzysty cykl
            result *= power_of_two();
        else
            result *= binomial();
            
        result %= modulo;
    }
    
    cout<<result<<endl;

    return 0;
}