#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <queue>
#include <ctime>
#include <stack>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
template <class T> void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template <class T> void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }

const int N = 1005;
const lld INF = (lld)(1e18);
int n;
char s[N * 2];
int op[N * 2];

struct Node {
	vector <Node *> E;
	int key;
	lld f[2];
	bool c;
	lld mul;

	bool gc;
	lld gf[2];
}sp[N + N], *root;

int spt;

lld mul(lld x, lld y) {
	if (y == 0) return 0;
	if ((double)x*y >= INF ) {
		return INF;
	} else {
		return x * y;
	}
}

int readNum(int i, int e) {
	int ret = 0;
	for ( ; i <= e; i++) {
		if (s[i] >= '0' && s[i] <= '9') {
			ret = ret * 10 + s[i] - '0';
		} else {
			break;
		}
	}
	return ret;
}

void build(Node *&p, int l, int r) {
	while (op[l] == r){ l++; r--; }
	p = &sp[spt++];
	p->E.clear();
	p->mul = 1;
	for (int i = l; i <= r; i++) {
		if (s[i] == '(') {
			int _l = i;
			int _r = op[i];
			p->E.push_back(NULL);
			build(p->E[p->E.size() - 1], _l, _r);
			i = op[i];
			while (!(s[i] >= '0' && s[i] <= '9')) i++;
			int x = readNum(i, r);
			p->E[p->E.size() - 1]->mul = x;
			while (s[i] >= '0' && s[i] <= '9') i++;
		} else if (s[i] >= '0' && s[i] <= '9') {
			Node *q = &sp[spt++];
			q->E.clear();
			q->key = readNum(i, r);
			q->mul = 1;
			p->E.push_back(q);
			while (s[i] >= '0' && s[i] <= '9') i++;
		}
	}
}

void gao() {
	spt = 0;
//	memset(sp, 0, sizeof(sp));
	memset(op, 0xFF, sizeof(op));
	int m = strlen(s);
	stack <int> st;
	for (int i = 0; i < m; i++) {
		if (s[i] == '(') {
			st.push(i);
		} else if (s[i] == ')') {
			op[i] = st.top();
			op[st.top()] = i;
			st.pop();
		}else op[i] = -1;
	}
	build(root, 0, m - 1);
}

void dfs(Node *p) {
	int cnt = 0;
	foreach (it, p->E) {
		Node *q = *it;
		dfs(q);
		cnt++;
	}
	if (!cnt) {
		if (p->mul & 1) {
			p->c = 1;
			p->f[0] = mul(p->mul / 2, p->key);
			p->f[1] = mul(p->mul / 2 + 1, p->key);
			p->gc = 1;
			p->gf[0] = 0;
			p->gf[1] = p->key;
		} else {
			p->c = 0;
			p->f[0] = mul(p->mul / 2, p->key);
			p->f[1] = mul(p->mul, p->key);
			p->gc = 1;
			p->gf[0] = 0;
			p->gf[1] = p->key;
		}
	} else {
		p->c = 0;
		p->f[0] = p->f[1] = 0;
		foreach (it, p->E) {
			Node *q = *it;
			if (p->c) {
				p->f[0] += q->f[1];
				p->f[1] += q->f[0];
			} else {
				p->f[0] += q->f[0];
				p->f[1] += q->f[1];
			}
			p->c ^= q->c;
		}
		p->gc = p->c;
		p->gf[0] = p->f[0];
		p->gf[1] = p->f[1];
		if (p->c) {
			if (p->mul & 1) {
				long long sum = mul(p->f[0] + p->f[1], p->mul / 2);
				p->f[0] += sum;
				p->f[1] += sum;
			} else {
				p->c = 0;
				long long sum = mul(p->f[0] + p->f[1], p->mul / 2);
				p->f[0] = p->f[1] = sum;
			}
		} else {
			p->f[0] = mul(p->f[0], p->mul);
			p->f[1] = mul(p->f[1], p->mul);
		}
	}
}

void make_f() {
	dfs(root);
}

long long ans;

void finalgao(Node *p, bool o) {
	if (p->gc) {
		if (!p->gf[1 ^ o]) {
			ans += p->gf[0 ^ o];
			o ^= 1;
		}
		if (!p->gf[0 ^ o]) {
			lld c = (n - 1) / p->gf[1 ^ o];
			if (c > 0) {
				n -= c * p->gf[1 ^ o];
				ans += (c * 2 - 1) * p->gf[1 ^ o];
				o ^= 1;
			}
		} else {
			lld c = (n - 1) / (p->gf[0] + p->gf[1]);
			if (c > 0) {
				n -= c * (p->gf[0] + p->gf[1]);
				ans += c * (p->gf[0] + p->gf[1]) * 2;
			}
		}
	} else {
		lld c = (n - 1) / p->gf[1 ^ o];
		ans += c * (p->gf[0] + p->gf[1]);
		n -= c * p->gf[1 ^ o];
	}
	if (n > p->gf[1 ^ o] && n) {
		ans += p->gf[0] + p->gf[1];
		n -= p->gf[1 ^ o];
		o ^= p->gc;
	}
	if (!p->E.empty()) {
		foreach (it, p->E) {
			Node *q = *it;
			if (q->f[1 ^ o] >= n) {
				finalgao(q, o);
				return;
			} else {
				ans += q->f[0] + q->f[1];
				n -= q->f[1 ^ o];
				o ^= q->c;
			}
		}
	} else {
		ans += n;
	}
}

void get_ans() {
	lld c = (n - 1) / root->f[1];
	ans = c * (root->f[0] + root->f[1]);
	n -= c * root->f[1];
	finalgao(root, 0);
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	for (;;) {
		gets(s);
		sscanf(s, "%d", &n);
		if (n == 0) break;
		gets(s);
		int m = strlen(s);
		if (m>=1000) break;
		int cnt = m;
		s[cnt++] = ' ';
		for (int i = 0; i < m; i++) {
			s[cnt++] = s[i];
		}
		s[cnt] = 0;
		gao();
		make_f();
		get_ans();
		printf("%lld\n", ans);
	}
}