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

const int mod = 1000 * 1000 * 1000 + 7;

struct drz {
	drz *l;
	drz *p;
	long long int v;
	drz() {
		l = NULL;
		p = NULL;
		v = 1;
	}
	long long lew() {
		if (l == NULL) return 0;
		return l -> v;
	}
	long long pra() {
		if (p == NULL) return 0;
		return p -> v;
	}
};


drz * root;

void dodaj_nowy_korzen () {
	drz *r = root;
	root = new drz();
	root -> l = r;
	root -> p = r;
	root -> v = (root -> lew() + root -> pra()) % mod;
}

const int N = 1000 * 1000 + 5;

vector< vector<pair<int,bool> > > wyrazenia;
vector<pair<int,bool> > empty;

drz* wstaw(const vector<pair<int,bool> >& z, int id, drz* v) {
	drz* result = new drz();
	result -> l = v -> l;
	result -> p = v -> p;
	if (v -> v == 0 || id == (int)z.size()) {
		result -> v = 0;
	}
	else {
		if (z[id].second) {
			result -> l = wstaw(z, id+1, v -> l);
		} else {
			result -> p = wstaw(z, id+1, v -> p);
		}
		result -> v = (result -> lew() + result -> pra()) % mod;
	}
	return result;
}

const int BUF_SIZE = 1000 * 1000 * 20;
char bufor[BUF_SIZE];

bool jest_cyfra(char x) {
	return x <= '9' && x >= '0';
}

int main() {
	int n;
	scanf("%d\n", &n);
	fgets(bufor, BUF_SIZE, stdin);
	int size = strlen(bufor);
	int beg = 0;
	while(beg < size) {
		bool znak = true;
		if (bufor[beg] == '(') {
			wyrazenia.push_back(empty);
		}
		if (bufor[beg] == '~') {
			beg ++;
			znak = false;
		}
		if (bufor[beg] == 'x') {
			beg ++;
			int numer_zmiennej = 0;
			while(jest_cyfra(bufor[beg])) {
				numer_zmiennej *= 10;
				numer_zmiennej += bufor[beg] - '0';
				beg ++;
			}
			wyrazenia.back().push_back(make_pair(numer_zmiennej, znak));
			beg --;
		}
		beg ++;
	}
	for (auto &v: wyrazenia) {
		sort(v.begin(), v.end());
	}
	sort(wyrazenia.begin(), wyrazenia.end(),
		[](const vector<pair<int, bool> >& a, const vector<pair<int, bool> >& b) {
			return a[0] < b[0];
		});
	root = new drz();
// 	printf("wyrazen %d\n", wyrazenia.size());
// 	for (auto v: wyrazenia) {
// 		for (auto x: v) {
// 			printf("%d %d, ", x.first, x.second);
// 		}
// 		printf("\n");
// 	}
	int id = wyrazenia.size() - 1;
	for (int x = n; x >= 1; x --) {
		dodaj_nowy_korzen();
// 		printf("%d -- %lld\n", x, root->v);
// 		printf("szukaj wyrazenia %d\n", wyrazenia[id][0].first);
		while (id >= 0 && wyrazenia[id][0].first == x) {
			root = wstaw(wyrazenia[id], 0, root);
// 			printf("inside %d -- %lld\n", x, root->v);
			id --;
		}
// 		printf("%d -- %lld\n", x, root->v);
	}
	printf("%lld\n", root -> v);
}