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
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int MN = 1000005, INF = 1000000005;

string opis;

vector <int> co[MN], kon[MN];
int akt[MN], pocz[MN], C[MN];

int parsuj()
{
	int l = opis.length();
	int curr, maxi, mini, kozdra, liczba, val;
	curr = maxi = mini = kozdra = liczba = val = 0;
	maxi = -1;
	opis[l++] = '(';
	for(int i = 0; i < l; ++i)
	{
		if(opis[i] == '(')
		{
			//printf("%d %d\n", mini, maxi);
			for(int j = mini; j <= maxi; ++j)
				co[curr].pb(akt[j]);
			pocz[curr] = mini;
			kon[maxi].pb(curr);
			++curr;
			maxi = 0;
			mini = INF;
		}
		if(opis[i] == '~')
			kozdra = 1;
		if(opis[i] == 'x')
		{
			liczba = 1;
			val = 0;
		}
		if((opis[i] == ' ' || opis[i] == ')') && liczba)
		{
			akt[val] = kozdra;
			maxi = max(maxi, val);
			mini = min(mini, val);
			liczba = 0;
			val = 0;
			kozdra = 0;
		}
		if(liczba && (opis[i] >= '0' && opis[i] <= '9') )
		{
			val *= 10;
			val += (opis[i] - '0');
		}
	}
	return curr;
}

int wynig;
int n;

bool check(int p)
{
	int s = kon[p].size();
	int ok;
	int xx, ss;
	for(int i = 0; i < s; ++i)
	{
		ok = 0;
		xx = kon[p][i];
		ss = p;
		while(ss >= pocz[xx])
		{
			ok |= ((int)(C[ss] == co[xx][ss - pocz[xx]]));
			--ss;
		}
		if(!ok)
			return false;
	}
	return true;
}

void backtrack(int p)
{
	C[p] = 0;
	if(check(p))
	{
		if(p == n)
			++wynig;
		else
			backtrack(p + 1);
	}
	C[p] = 1;
	if(check(p))
	{
		if(p == n)
			++wynig;
		else
			backtrack(p + 1);
	}
}

int main()
{
	scanf("%d", &n);
	getline(cin, opis);
	getline(cin, opis);
	int m = parsuj();
	backtrack(1);
	printf("%d", wynig);
}