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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct ciag
{
	int pocz;
	int kon;
	int war;
	vector<int> v;
};
ciag t[1000005];
string s;
int n, il=0, a, mini=1000005, maks, pos=1, dop[1000005], mod=1000000007;
bool b[2][1000005];
bool cmp(ciag x, ciag y)
{
	if(x.pocz>y.pocz) return 0;
	else if(x.pocz==y.pocz)
	{
		if(x.kon>y.kon) return 0;
		else return 1;
	}
	else return 1;
}
int pot(int x)
{
	if(x==0) return 1;
	if(x%2==1) return (2*pot(x-1))%mod;
	long long w=pot(x/2);
	return (w*w)%mod;
}
int main()
{
	scanf("%d", &n);
	cin.ignore();
	getline(cin,s);
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='(')
		{
			t[il].pocz=mini;
			t[il].kon=maks;
			mini=1000005;
			maks=0;
		    il+=1;
		}
		else if(s[i]=='~')
		{
			i+=2;
			a=0;
			while(s[i]-'0'<10 && s[i]-'0'>=0)
			{
				a*=10;
				a+=s[i]-'0';
				i+=1;
			}
			a=-a;
			t[il].v.push_back(a);
			mini=min(mini,-a);
			maks=max(maks,-a);
		}
		else if(s[i]-'0'<10 && s[i]-'0'>=0)
		{		
			a=0;
			while(s[i]-'0'<10 && s[i]-'0'>=0)
			{
				a*=10;
				a+=s[i]-'0';
				i+=1;
			}
			t[il].v.push_back(a);
			mini=min(mini,a);
			maks=max(maks,a);
		}
	}
	t[il].pocz=mini;
	t[il].kon=maks;
	t[il+1].kon=1000005;
	t[il+1].pocz=1000005;
	sort(t+1,t+il+1,cmp);
	for(int i=1;i<=il+1;i++)
	{
		for(int j=pos;j<t[i].pocz;j++) dop[j]=i;
		pos=t[i].pocz;
	}
	for(int i=il;i>0;i--)
	{
		for(int j=0;j<t[i].v.size();j++)
		if(t[i].v[j]<0) b[0][-t[i].v[j]]=1;
		else  b[1][t[i].v[j]]=1;
		for(int j=t[i].kon;j>=t[i].pocz;j--)
		if(j<=t[i+1].kon)
		{
			if(dop[j]==il+1) t[i].war+=pot(n-j);
			else t[i].war+=t[dop[j]].war;
			if(b[0][j] && b[1][j]) t[i].war-=1;
			t[i].war=t[i].war%mod;
		}
	}
	printf("%d", t[1].war);
	return 0;
}