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
#include<iostream>
#include<set>
#include<algorithm>
#include<cmath>
#include <cctype>
using namespace std;
const int N=1000002;
int tab[N];
set <int> prawda[N], falsz[N], pojedyncze;
set <int> :: iterator it;
int n, i, j = -1, w = 0, k = 0,x;
string formula;
bool b = true;
long long wynik = 1;

int main()
{
ios_base::sync_with_stdio(0);
cin >> n;
cin >> formula;
i = 0;
while( i < formula.size()) {
	if(formula[i] == '(') {
		++i;
		while(formula[i] != ')'){
			if(formula[i] == '~') b = false;
			else if(formula[i] == 'x') w = 0;
			else if (isdigit(formula[i]) ) w = w*10 + (formula[i] -'0');
			else if (formula[i] == 'v' || formula[i] == ')')
				if ( b == true) {
						prawda[k].insert(w);
						w = 0;
					}
					else {
						falsz[k].insert(w);
						b = true;
						w = 0;
					}
		++i;	
		}
		if ( b == true) {
						prawda[k].insert(w);
						w = 0;
					}
					else {
						falsz[k].insert(w);
						b = true;
						w = 0;
					}
		k++;
		//cout <<" k"  << k <<"  ";
	}
	++i;
}
for(i=0; i < k;++i)	if( (prawda[i].size()+falsz[i].size()) ==1) {
	//cout <<" i"  << i <<"  ";
pojedyncze.insert(i);
	}
/*for(i=0; i < k;++i)	 {
	cout <<i<<":";
	for(it = prawda[i].begin(); it!=prawda[i].end();++it) cout << *it <<" "; 
	cout << endl;
}*/
while(!pojedyncze.empty()){
	it = pojedyncze.begin();
	j = *it;
	//cout << j <<" ";	
	pojedyncze.erase(it);
	if(prawda[j].size()>0) {
		x = *prawda[j].begin();
		//cout <<" xp "  << x <<"  ";
		tab[x] = 1;
		for(i=0; i < k;++i) if(falsz[i].find(x) != falsz[i].end()) {
			falsz[i].erase(falsz[i].find(x));
			if(falsz[i].size()==1) pojedyncze.insert(i);
		}
		
		
	}
	else{
		x = *falsz[j].begin();
		tab[x] = 1;
		//cout <<" xf "  << x <<"  ";
		for(i=0; i < k;++i) if(prawda[i].find(x) != prawda[i].end()) {
			prawda[i].erase(prawda[i].find(x));
			if(prawda[i].size()==1) pojedyncze.insert(i);
		 }
		
	}
}

for(i = 1 ; i <= n; ++i) if(tab[i] == 0) wynik= (wynik *2)%1000000007;
cout << wynik;
return 0; 
}