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
#include<iostream>
#include<vector>
using namespace std;

#define MAX 1000000+7

bool T[MAX];
bool B[MAX];


struct exp{
	int n;
	bool opp;
};

struct formula{
	int p, q;
	vector<exp> V;
};

long long result;

void check(int i, vector<formula> &F, int n) {
	
	if(i==n+1) {
		
		for(int j=0; j<F.size(); j++) {
			bool c = false;
			for(int k=0; k<F[j].V.size(); k++)
				if(  (B[F[j].V[k].n] && !F[j].V[k].opp) || (!B[F[j].V[k].n] && F[j].V[k].opp) )
					c = true;
			if(!c) return;
		}
		result++;
		return;
	}
	
	if(T[i]) {
		B[i] = true;
		check(i+1, F, n);
		B[i] = false;
		check(i+1, F, n);
	
	} else {
	check(i+1, F, n);
}
}

int main() {
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	string f;
	getline(cin, f);
	getline(cin, f);
	//cin>>f;
	bool form = false;
	exp e;
	vector< formula > F;
	
	
	for(int i=1; i<=n; i++)
		T[i] = false;

	result = 0;
	e.n = -1;
	formula A;
	for(int i=0; i<f.length(); i++) {
	
		if(form) {
			if( f[i] >= '0' && f[i] <= '9') {
				int a = f[i] - '0';
				e.n *= 10;
				e.n += a;
			} 
			else
			switch( f[i] ) {
				case 'x':
					e.n = 0;
					break;
				case 'v':
					if(e.n >= 0) {
						A.V.push_back(e);
						T[e.n] = true;
					}
					//cout<<e.n<<endl;
					e.opp = false;
					break;
				case '~':
					e.opp = true;
					break;
				case ')':
					form = false;
					A.V.push_back(e);
					e.opp = false;
					T[e.n] = true;
					F.push_back(A);
					A.V.clear();
					//proceed
					break;
			}
		} else 
		if( f[i] == '(') {
			form = true;
			//continue;
		}
		
	}
	check(1, F, n);
	cout<<result<<endl;
	return 0;
}