mauricio

#include <bits/stdc++.h>
using namespace std;
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d %d", &a, &b)
#define sc3(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define pri(x) printf("%d\n", x)
#define prie(x) printf("%d ", x)
#define mp make_pair
#define pb push_back
#define BUFF ios::sync_with_stdio(false);
#define db(x) cerr << #x << " == " << x << endl;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const ld pi = acos(-1);
const int MOD = 30011;
vi divip;
typedef vector<ll> poly;
template <typename T> class Karatsuba {
  typedef typename vector<T>::iterator vTi;
  int cut;
  void convolve_naive(vTi a, vTi b, vTi c, int n) {
    int n2 = n * 2;
    for (int i = 0; i < n2; ++i)
      c[i] = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        c[i + j] += a[i] * b[j];
  }
  void karatsuba(vTi a, vTi b, vTi c, int n) {
    if (n <= cut) {
      convolve_naive(a, b, c, n);
      return;
    }
    int nh = n / 2;
    vTi al = a, ah = a + nh, as = c + nh * 10;
    vTi bl = b, bh = b + nh, bs = c + nh * 11;
    vTi x0 = c, x1 = c + n, x2 = c + n * 2, xh = c + nh;
    for (int i = 0; i < nh; ++i) {
      as[i] = al[i] + ah[i];
      bs[i] = bl[i] + bh[i];
    }
    karatsuba(al, bl, x0, nh);
    karatsuba(ah, bh, x1, nh);
    karatsuba(as, bs, x2, nh);
    for (int i = 0; i < n; ++i)
      x2[i] -= x0[i] + x1[i];
    for (int i = 0; i < n; ++i)
      xh[i] += x2[i];
  }

public:
  Karatsuba(int _cut = 1 << 5) : cut(_cut) {}
  vector<T> convolve(vector<T> &_a, vector<T> &_b) {
    vector<T> a = _a, b = _b, c;
    int sz = max(a.size(), b.size()), sz2;
    for (sz2 = 1; sz2 < sz; sz2 *= 2)
      ;
    a.resize(sz2);
    b.resize(sz2);
    c.resize(sz2 * 6);
    karatsuba(a.begin(), b.begin(), c.begin(), sz2);
    c.resize(_a.size() + _b.size() - 1);
    return c;
  }
};

vector<ll> convolution(vector<ll> cara1, vector<ll> cara2) {
  Karatsuba<ll> kt;
  return kt.convolve(cara1, cara2);
}
int mapa[200200], remapa[200200];
int P;
poly trad(poly &lista1) {
  poly trad(P, 0);
  trad[0] = 0;
  for (int i = 1; i < P; i++) {
    trad[mapa[i]] = lista1[i];
  }
  return trad;
}
poly retrad(poly &lista1) {
  vector<ll> ret(P, 0);
  for (int i = 1; i < P; i++) {
    ret[remapa[i]] = lista1[i];
  }
  return ret;
}
poly merge_mul(poly lista1, poly lista2) {
  poly cara1 = trad(lista1);
  poly cara2 = trad(lista2);
  ll sumcara2 = 0;
  for (ll x : lista2)
    sumcara2 += x;
  ll sumcara1 = 0;
  for (ll x : lista1)
    sumcara1 += x;
  ll zero = (lista1[0]) * sumcara2;
  ll zero2 = (lista2[0]) * (sumcara1 - lista1[0]);
  zero = (zero + zero2) % MOD;
  poly respi = convolution(cara1, cara2);
  poly vai(P, 0);
  for (int i = 1; i < P; i++) {
    vai[i] = (respi[i] + respi[i + P - 1]) % MOD;
  }
  poly ret = retrad(vai);
  ret[0] = zero;
  return ret;
}
poly merge_add(poly lista1, poly lista2) {
  poly respi = convolution(lista1, lista2);
  poly ret(P, 0);
  for (int i = 0; i < P - 1; i++)
    ret[i] = (respi[i] + respi[i + P]) % MOD;
  ret[P - 1] = respi[P - 1];
  return ret;
}
int powe(int, int, int);
poly merge_pot(poly lista1, int pot) {
  poly cara(P, 0);
  for (int i = 0; i < (int)lista1.size(); i++) {
    int idx = powe(i, pot, P);
    cara[idx] = (lista1[i] + cara[idx]) % MOD;
  }
  return cara;
}

struct node {
  char op = ' ';      //  *^+.
  int x = -2;         // se for literal é -1, se for constante é entre 0 e 9
  int l = -1, r = -1; // filho esquerda e direita
  int p;              // pai
  node() { op = ' ', x = -2, l = -1, r = -1; }
};
node tree[410];

poly eval(int root) {
  if (tree[root].op == '.') {
    if (tree[root].x == -1) {
      poly num(P, 1);
      return num;
    } else {
      poly num(P, 0);
      assert(tree[root].x >= 0);
      num[tree[root].x % P] = 1;
      return num;
    }
  } else if (tree[root].op == '*') {
    return merge_mul(eval(tree[root].l), eval(tree[root].r));
  } else if (tree[root].op == '+') {
    return merge_add(eval(tree[root].l), eval(tree[root].r));
  } else if (tree[root].op == '^') {
    assert(tree[tree[root].r].x >= 2);
    return merge_pot(eval(tree[root].l), tree[tree[root].r].x);
  } else {
    assert(false);
  }
}

void parse(string &s) {
  int tot = 0;
  int curr = 0;
  for (char c : s) {
    if (c == '(') {
      if (tree[curr].l == -1) { // novo filho esquerda
        int nxt = ++tot;
        tree[curr].l = nxt;
        tree[nxt].p = curr;
        curr = nxt;
      } else { // novo filho direita
        int nxt = ++tot;
        tree[curr].r = nxt;
        tree[nxt].p = curr;
        curr = nxt;
      }
    } else if (c == '*' or c == '+' or c == '^') {
      curr = tree[curr].p;
      tree[curr].op = c;
      assert(tree[curr].r == -1);
      int nxt = ++tot;
      tree[curr].r = nxt;
      tree[nxt].p = curr;
      curr = nxt;

    } else if (c != ')') {
      int x;
      if (c >= 'a' and c <= 'z')
        x = -1; // variavel
      else
        x = c - '0';
      tree[curr].op = '.';
      tree[curr].x = x;

    } else {
      curr = tree[curr].p;
    }
    assert(curr != -1);
    // cout << c << " " << curr << endl;
  }
}
int prim[100100];
int powe(int b, int e, int mod) {
  if (e == 0)
    return 1;
  if (e & 1)
    return (b * (ll)powe(b, e - 1, mod)) % mod;
  int x = powe(b, e / 2, mod);
  return (x * (ll)x) % mod;
}
int testa(int x, int p) {
  for (int y : divip) {
    if (powe(x, (p - 1) / y, p) == 1)
      return 0;
  }
  return 1;
}
int primitive_root(int p) {
  if (p == 2)
    return 1;
  for (int i = 2; i < p; i++) {
    if (testa(i, p))
      return i;
  }
  assert(false);
}
int main() {
  int p;
  cin >> p;
  string s;
  cin >> s;
  parse(s);
  P = p;
  for (int i = 2; i < 100100; i++)
    if (!prim[i])
      for (int j = 2 * i; j < 100100; j += i)
        prim[j] = 1;

  for (int i = 2; i <= p; i++) {
    if (!prim[i] and (p - 1) % i == 0) {
      divip.pb(i);
    }
  }
  int root = primitive_root(p);
  set<int> gen;
  for (int i = 1; i < p; i++)
    gen.insert(powe(root, i, p));
  assert(gen.size() == p - 1);
  for (int i = 1; i <= p - 1; i++) {
    mapa[i] = powe(root, i, p);
    remapa[powe(root, i, p)] = i;
  }
  poly coco = eval(0);
  pri((int)coco[0]);
}